<!DOCTYPE html>
<html>
<head>
  <meta charset="utf-8">
  
  <title>Eetal&#39;s Blog</title>

  <!-- keywords -->
  

  <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
  <meta name="description" content="The eetal&apos;s hexo blog in gitee">
<meta property="og:type" content="website">
<meta property="og:title" content="Eetal&#39;s Blog">
<meta property="og:url" content="http://eetal.gitee.io/blog/page/2/index.html">
<meta property="og:site_name" content="Eetal&#39;s Blog">
<meta property="og:description" content="The eetal&apos;s hexo blog in gitee">
<meta property="og:locale" content="default">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="Eetal&#39;s Blog">
<meta name="twitter:description" content="The eetal&apos;s hexo blog in gitee">
  
    <link rel="alternative" href="/atom.xml" title="Eetal&#39;s Blog" type="application/atom+xml">
  
  
    <link rel="icon" href="http://www.yangyitao.top/FiveChess/resource/ico/favicon.ico">
  
  <link rel="stylesheet" href="/blog/css/style.css">
  
  

  <script src="//cdn.bootcss.com/require.js/2.3.2/require.min.js"></script>
  <script src="//cdn.bootcss.com/jquery/3.1.1/jquery.min.js"></script>

  
</head>
<body>
  <div id="container">
    <div id="particles-js"></div>
    <div class="left-col">
    <div class="overlay"></div>
<div class="intrude-less">
	<header id="header" class="inner">
		<a href="/" class="profilepic">
			
			<img lazy-src="/blog/images/head.jpg" class="js-avatar">
			
		</a>

		<hgroup>
		  <h1 class="header-author"><a href="/">Eetal</a></h1>
		</hgroup>

		
		<p class="header-subtitle">java coder</p>
		

		
			<div class="switch-btn">
				<div class="icon">
					<div class="icon-ctn">
						<div class="icon-wrap icon-house" data-idx="0">
							<div class="birdhouse"></div>
							<div class="birdhouse_holes"></div>
						</div>
						<div class="icon-wrap icon-ribbon hide" data-idx="1">
							<div class="ribbon"></div>
						</div>
						
						<div class="icon-wrap icon-link hide" data-idx="2">
							<div class="loopback_l"></div>
							<div class="loopback_r"></div>
						</div>
						
						
					</div>
					
				</div>
				<div class="tips-box hide">
					<div class="tips-arrow"></div>
					<ul class="tips-inner">
						<li>菜单</li>
						<li>标签</li>
						
						<li>友情链接</li>
						
						
					</ul>
				</div>
			</div>
		

		<div class="switch-area">
			<div class="switch-wrap">
				<section class="switch-part switch-part1">
					<nav class="header-menu">
						<ul>
						
							<li><a href="/blog/">Home</a></li>
				        
							<li><a href="/blog/archives">Archives</a></li>
				        
						</ul>
					</nav>
					<nav class="header-nav">
						<div class="social">
							
						</div>
					</nav>
				</section>
				
				
				<section class="switch-part switch-part2">
					<div class="widget tagcloud" id="js-tagcloud">
						
					</div>
				</section>
				
				
				
				<section class="switch-part switch-part3">
					<div id="js-friends">
					
			          <a target="_blank" class="main-nav-link switch-friends-link" href="https://github.com/smackgg/hexo-theme-smackdown">smackdown</a>
			        
			        </div>
				</section>
				

				
			</div>
		</div>
	</header>				
</div>
    </div>
    <div class="mid-col">
      <nav id="mobile-nav">
  	<div class="overlay">
  		<div class="slider-trigger"></div>
  		<h1 class="header-author js-mobile-header hide">Eetal</h1>
  	</div>
	<div class="intrude-less">
		<header id="header" class="inner">
			<div class="profilepic">
				<img lazy-src="/blog/images/head.jpg" class="js-avatar">
			</div>
			<hgroup>
			  <h1 class="header-author">Eetal</h1>
			</hgroup>
			
			<p class="header-subtitle">java coder</p>
			
			<nav class="header-menu">
				<ul>
				
					<li><a href="/blog/">Home</a></li>
		        
					<li><a href="/blog/archives">Archives</a></li>
		        
		        <div class="clearfix"></div>
				</ul>
			</nav>
			<nav class="header-nav">
				<div class="social">
					
				</div>
			</nav>
		</header>				
	</div>
</nav>
      <div class="body-wrap">
  
    <article id="post-动态代理与静态代理" class="article article-type-post" itemscope itemprop="blogPost">
  
    <div class="article-meta">
      <a href="/blog/2019/04/07/动态代理与静态代理/" class="article-date">
  	<time datetime="2019-04-07T15:41:21.467Z" itemprop="datePublished">2019-04-07</time>
</a>
    </div>
  
  <div class="article-inner">
    
      <input type="hidden" class="isFancy" />
    
    
      <header class="article-header">
        
  
    <h1 itemprop="name">
      <a class="article-title" href="/blog/2019/04/07/动态代理与静态代理/">
        动态代理与静态代理
        
      </a>
    </h1>
  

      </header>
      
    
    <div class="article-entry" itemprop="articleBody">
      
        <p>欢迎查看Eetal的第十七篇博客–动态代理与静态代理</p>
<h2 id="静态代理—硬编码"><a href="#静态代理—硬编码" class="headerlink" title="静态代理—硬编码"></a>静态代理—硬编码</h2><p>没啥好说的，就是像装饰模式一样</p>
<figure class="highlight bash"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br></pre></td><td class="code"><pre><span class="line">public class StaticProxy extends Object&#123;</span><br><span class="line">	</span><br><span class="line">	Object object;</span><br><span class="line">	</span><br><span class="line">	public StaticProxy(Object object) &#123;</span><br><span class="line">		this.object = object;</span><br><span class="line">	&#125;</span><br><span class="line">	</span><br><span class="line">	@Override</span><br><span class="line">	public int <span class="function"><span class="title">hashCode</span></span>() &#123;</span><br><span class="line">		System.out.println(<span class="string">"proxy decorate start..."</span>);</span><br><span class="line">		int hashCode = object.hashCode();</span><br><span class="line">		System.out.println(<span class="string">"proxy decorate end..."</span>);</span><br><span class="line">		<span class="built_in">return</span> hashCode;</span><br><span class="line">	&#125;</span><br><span class="line">	</span><br><span class="line">	public static void main(String[] args) &#123;</span><br><span class="line">		Object proxy = new StaticProxy(new Object());</span><br><span class="line">		System.out.println(proxy.hashCode());</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="动态代理"><a href="#动态代理" class="headerlink" title="动态代理"></a>动态代理</h2><h3 id="JDK动态代理—反射、Proxy、InvocationHandler"><a href="#JDK动态代理—反射、Proxy、InvocationHandler" class="headerlink" title="JDK动态代理—反射、Proxy、InvocationHandler"></a>JDK动态代理—反射、Proxy、InvocationHandler</h3><p>jdk动态代理要求对象必须实现接口<br>并且仅会代理接口方法以及equals，hashCode和toString三个Object类的方法<br>生成的代理类也仅是实现这些接口和继承Proxy所以接口里没有的方法在代理对象里不存在<br><figure class="highlight bash"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br></pre></td><td class="code"><pre><span class="line">public class DynamicProxy &#123;</span><br><span class="line">	static class BAInvocationHandler implements InvocationHandler&#123;</span><br><span class="line">		</span><br><span class="line">		private Object realObj;</span><br><span class="line">		</span><br><span class="line">		public BAInvocationHandler(Object realObj) &#123;</span><br><span class="line">			this.realObj = realObj;</span><br><span class="line">		&#125;</span><br><span class="line">		</span><br><span class="line">		public void <span class="function"><span class="title">doBefore</span></span>() &#123;</span><br><span class="line">			System.out.println(<span class="string">"before ..."</span>);</span><br><span class="line">		&#125;</span><br><span class="line">		</span><br><span class="line">		public void <span class="function"><span class="title">doAfter</span></span>() &#123;</span><br><span class="line">			System.out.println(<span class="string">"after ..."</span>);</span><br><span class="line">		&#125;</span><br><span class="line">		</span><br><span class="line">		@Override</span><br><span class="line">		public Object invoke(Object proxy, Method method, Object[] args) throws Throwable &#123;</span><br><span class="line">			//proxy为代理对象，所以此处不能调用proxy的方法否则会栈溢出死锁</span><br><span class="line">			//proxy是在newProxyInstance时生成并在调用时传进来的，因为invocationHandler与Proxy是聚合模式</span><br><span class="line">			//所以在invocation中获取不到代理对象，只能通过这种方式传递进来</span><br><span class="line">			doBefore();</span><br><span class="line">			Object result = method.invoke(realObj, args);</span><br><span class="line">			System.out.println(<span class="string">"invoke result :"</span>+result);</span><br><span class="line">			doAfter();</span><br><span class="line">			<span class="built_in">return</span> result;</span><br><span class="line">		&#125;</span><br><span class="line"></span><br><span class="line">	&#125;</span><br><span class="line">	static &lt;T&gt;T getInstance(Object realObj,Class&lt;T&gt;... clazz) &#123;</span><br><span class="line">		//第一个T泛型方法</span><br><span class="line">		//clazz 该代理类实现的接口</span><br><span class="line">		<span class="built_in">return</span> (T)Proxy.newProxyInstance(clazz[0].getClassLoader(), clazz,new BAInvocationHandler(realObj));</span><br><span class="line">	&#125;</span><br><span class="line">	public static void main(String[] args) &#123;</span><br><span class="line">		Object o = getInstance(new Object(),Serializable.class);</span><br><span class="line">		o.hashCode();</span><br><span class="line">		System.out.println(o instanceof Proxy);</span><br><span class="line">		</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<p>由于jdk动态代理基于接口的特性，使得其只能代理接口对象的方法，也就是必须实现接口<br>至于为什么，我个人的理解是在运行时<br>1.其要继承Proxy，因为Proxy封装了动态代理的底层实现，所以Proxy不能是接口，因此只能通过继承来组合（通过聚合或者组合还是离不开要修改字节码）<br>2.jdk反射只能得到每一个class，interface等的field的名称，返回值类型，形参类型，方法体是得不到的，<br>否则就得通过读取修改字节码来生成新的class的字节码文件(cglib就是这么做的)，而读取解析修改字节码效率肯定低一点<br>因此jdk代理只代理接口对象，实际需要一个原对象，再生成一个代理对象，使用的是代理对象<br>注意是对象因为原对象一些在接口中不存在的属性在代理对象中是不存在的，这也是需要getter、setter存在的一个原因</p>
<h3 id="CGLIB动态代理—修改字节码，生成新的子类Class"><a href="#CGLIB动态代理—修改字节码，生成新的子类Class" class="headerlink" title="CGLIB动态代理—修改字节码，生成新的子类Class"></a>CGLIB动态代理—修改字节码，生成新的子类Class</h3><p>当面对特殊的场景，比如就是没有实现任何接口，或者希望获取到所有属性，得到一个子类型的类型，就需要通过cglib了<br>cglib的做法是，通过读取修改字节码，创建一个继承了原有class的子类，所以cglib是代理类，代理方法，而不是代理对象<br>cglib会代理方法中所有不是final类型的非静态方法方法（因为静态方法不会使用代理对象和代理类）<br>使用时是直接使用代理类去创建对象，只有一个对象，因此效率较jdk代理低一点<br>在spring中就是根据要代理的类是否有实现接口，而决定使用cglib还是jdk动态代理<br><figure class="highlight bash"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br></pre></td><td class="code"><pre><span class="line">public class CGLIBDynamicProxy &#123;</span><br><span class="line">	static class Test&#123;</span><br><span class="line">		public final void <span class="function"><span class="title">finalMethod</span></span>() &#123;</span><br><span class="line">			System.out.println(<span class="string">"final"</span>);</span><br><span class="line">		&#125;</span><br><span class="line">		public void <span class="function"><span class="title">method</span></span>() &#123;</span><br><span class="line">			System.out.println(<span class="string">"method"</span>);</span><br><span class="line">		&#125;</span><br><span class="line">		public static void <span class="function"><span class="title">staticMethod</span></span>()&#123;</span><br><span class="line">			System.out.println(<span class="string">"staticMethod..."</span>);</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	static class BAInterceptor implements MethodInterceptor&#123;</span><br><span class="line">		</span><br><span class="line">		public void <span class="function"><span class="title">doBefore</span></span>() &#123;</span><br><span class="line">			System.out.println(<span class="string">"\nbefore ..."</span>);</span><br><span class="line">		&#125;</span><br><span class="line">		</span><br><span class="line">		public void <span class="function"><span class="title">doAfter</span></span>() &#123;</span><br><span class="line">			System.out.println(<span class="string">"after ...\n"</span>);</span><br><span class="line">		&#125;</span><br><span class="line"></span><br><span class="line">		@Override</span><br><span class="line">		public Object intercept(Object proxy, Method method, Object[] args, MethodProxy methodProxy) throws Throwable &#123;</span><br><span class="line">			//proxy---代理类对象</span><br><span class="line">			//method---代理后的方法</span><br><span class="line">			//args---参数</span><br><span class="line">			//methodProxy---方法的代理对象</span><br><span class="line">			//不能直接使用 method.invoke，因为会再调用invoke导致死锁stackOverFlow</span><br><span class="line">			doBefore();</span><br><span class="line">			//使用父类方法，也就是原类方法获取返回值</span><br><span class="line">			Object result = methodProxy.invokeSuper(proxy, args);</span><br><span class="line">			System.out.println(<span class="string">"invoke super result..."</span>+result);</span><br><span class="line">			doAfter();</span><br><span class="line">			<span class="built_in">return</span> result;</span><br><span class="line">		&#125;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line">	&#125;</span><br><span class="line">	static &lt;T&gt; T getInstance(Class&lt;T&gt; clazz) &#123;</span><br><span class="line">		//第一个T泛型方法</span><br><span class="line">		Enhancer enhancer = new Enhancer();</span><br><span class="line">		enhancer.setSuperclass(clazz);</span><br><span class="line">		enhancer.setCallback(new BAInterceptor());</span><br><span class="line">		<span class="built_in">return</span> (T) enhancer.create();</span><br><span class="line">	&#125;</span><br><span class="line">	public static void main(String[] args) &#123;</span><br><span class="line">		Test <span class="built_in">test</span> = getInstance(Test.class);</span><br><span class="line">		test.hashCode();</span><br><span class="line">		test.finalMethod();</span><br><span class="line">		test.method();</span><br><span class="line">		test.staticMethod();</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<h3 id="请移步"><a href="#请移步" class="headerlink" title="请移步"></a>请移步</h3><p>个人主页: <a href="http://yangyitao.top" target="_blank" rel="noopener">yangyitao.top</a></p>

      
    </div>
    
    <div class="article-info article-info-index">
      
      
      

      
      <div class="clearfix"></div>
    </div>
      
    
  </div>
  
</article>







  
    <article id="post-手撕B树" class="article article-type-post" itemscope itemprop="blogPost">
  
    <div class="article-meta">
      <a href="/blog/2019/04/03/手撕B树/" class="article-date">
  	<time datetime="2019-04-03T14:16:54.039Z" itemprop="datePublished">2019-04-03</time>
</a>
    </div>
  
  <div class="article-inner">
    
      <input type="hidden" class="isFancy" />
    
    
      <header class="article-header">
        
  
    <h1 itemprop="name">
      <a class="article-title" href="/blog/2019/04/03/手撕B树/">
        手撕B树
        
      </a>
    </h1>
  

      </header>
      
    
    <div class="article-entry" itemprop="articleBody">
      
        <p>欢迎查看Eetal的第十六篇博客–手撕B树</p>
<h2 id="B树"><a href="#B树" class="headerlink" title="B树"></a>B树</h2><p>B树和B+树都是多路查找树。具备分支多层数少的优点常用于数据库索引存储<br>BTree大量应用在数据库（mongodb）和文件系统当中，B+Tree经常用于数据库索引（空间局部性原理）<br>B树代表每个节点可存储的数据节点不超过m-1，且每个节点的子节点不超过m个的树。根节点的子节点为0或至少为2<br>B+树与B树区别就是B+树只在没有子节点的底层节点存储数据而其他包含子节点的父节点都是不存储数据值存储索引值<br>假设m为4我们就说这是一颗4叉的B树，其每个节点可以存储最多3个数据节点，最多含有4个子节点</p>
<h2 id="特点"><a href="#特点" class="headerlink" title="特点"></a>特点</h2><p>数据保存在节点<br>一个节点可以至有多m-1个数据节点<br>根结点如果有子女则至少有两个子女<br>除根结点以外的所有结点（不包括叶子结点）的度数正好是当前结点保存的数据节点总数加1，故内部子树个数 k 满足：┌m/2┐ &lt;= k &lt;= m<br>所有的叶子结点都位于同一层。（叶子节点指的是指向null）<br>每个非根节点所包含的数据节点个数 j 满足：┌m/2┐ - 1 &lt;= j &lt;= m - 1；// ┌m/2┐ ==》m/2向上取整</p>
<h2 id="结构图"><a href="#结构图" class="headerlink" title="结构图"></a>结构图</h2><p><img src="/blog/images/b-tree/b-tree.jpg" alt="b-tree"></p>
<h2 id="构造B树"><a href="#构造B树" class="headerlink" title="构造B树"></a>构造B树</h2><p>我们先了解下其几点重要构建要求<br>1.保持所有的叶子结点都位于同一层<br>2.一个节点可以至有多m-1个数据节点<br>3.每个非根节点所包含的数据节点个数 j 满足：┌m/2┐ - 1 &lt;= j &lt;= m - 1；// ┌m/2┐ ==》m/2向上取整<br>基于这些条件，B树的插入是从底部插入，先假设可以直接插入找到的节点，这时不破坏要求1<br>插入后因为新增数据节点如果破坏了要求2，进行裂变<br>裂变为了满足要求3从中间裂变<br>裂变出来的节点插入当前结点父节点（递归操作），因为是向上裂变插入，所以不破坏规则1</p>
<h2 id="代码实现"><a href="#代码实现" class="headerlink" title="代码实现"></a>代码实现</h2><p>可以保存多个数据节点的节点类<br><figure class="highlight bash"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line">class MultiNode&#123;</span><br><span class="line">	int nodeCounter = 0;//数据节点总数</span><br><span class="line">	Node head;//数据节点链表头</span><br><span class="line">	Node tail;//数据节点链表尾</span><br><span class="line">	MultiNode parent;//父节点</span><br><span class="line">	Node greaterParent;//大于当前节点的数据节点</span><br><span class="line">	Node lesserParent;//小于当前节点的数据节点</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<p>数据节点类<br><figure class="highlight bash"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line">class Node&#123;</span><br><span class="line">	int num;//索引大小</span><br><span class="line">	MultiNode greater;//大于</span><br><span class="line">	MultiNode lesser;//小于</span><br><span class="line">	Node prev;</span><br><span class="line">	Node next;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<p>裂变操作<br><figure class="highlight bash"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br></pre></td><td class="code"><pre><span class="line">private Node fissAndReturnBreakNode(MultiNode multiNode,int breakPoint) &#123;</span><br><span class="line">	<span class="keyword">if</span>(breakPoint&lt;1 || breakPoint&gt;=multiNums) &#123;</span><br><span class="line">		<span class="built_in">return</span> null;</span><br><span class="line">	&#125;</span><br><span class="line">	//裂变</span><br><span class="line">	<span class="keyword">if</span>(multiNode.greaterParent!=null) &#123;</span><br><span class="line">		//父节点断开</span><br><span class="line">		multiNode.greaterParent.lesser = null;</span><br><span class="line">		multiNode.greaterParent = null;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">if</span>(multiNode.lesserParent!=null) &#123;</span><br><span class="line">		//父节点断开</span><br><span class="line">		multiNode.lesserParent.greater = null;</span><br><span class="line">		multiNode.lesserParent = null;</span><br><span class="line">	&#125;</span><br><span class="line">	Node beakNode = multiNode.head;</span><br><span class="line">	<span class="keyword">for</span>(int i=0;i&lt;breakPoint;i++)</span><br><span class="line">		beakNode = beakNode.next;</span><br><span class="line">	MultiNode newMultiNode = new MultiNode();</span><br><span class="line">	newMultiNode.head = beakNode.next;</span><br><span class="line">	newMultiNode.tail = multiNode.tail;</span><br><span class="line">	multiNode.tail = beakNode.prev;</span><br><span class="line">	newMultiNode.nodeCounter = multiNode.nodeCounter - breakPoint -1;</span><br><span class="line">	multiNode.nodeCounter = breakPoint;</span><br><span class="line">	beakNode.next = beakNode.prev = newMultiNode.head.prev = multiNode.tail.next = null;</span><br><span class="line">	<span class="keyword">if</span>(beakNode.lesser!=null) &#123;</span><br><span class="line">		beakNode.lesser.lesserParent = multiNode.tail;</span><br><span class="line">		multiNode.tail.greater = beakNode.lesser;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">if</span>(beakNode.greater!=null) &#123;</span><br><span class="line">		beakNode.greater.greaterParent = newMultiNode.head;</span><br><span class="line">		newMultiNode.head.lesser = beakNode.greater;</span><br><span class="line">	&#125;</span><br><span class="line">	beakNode.lesser = multiNode;</span><br><span class="line">	multiNode.greaterParent = beakNode;</span><br><span class="line">	beakNode.greater = newMultiNode;</span><br><span class="line">	newMultiNode.lesserParent = beakNode;</span><br><span class="line">	newMultiNode.parent = multiNode.parent;</span><br><span class="line">	<span class="built_in">return</span> beakNode;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<p>插入操作<br><figure class="highlight bash"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br></pre></td><td class="code"><pre><span class="line">public void addNum(int num) &#123;</span><br><span class="line">	Node node = new Node();</span><br><span class="line">	node.num = num;</span><br><span class="line">	addNode(node,root);</span><br><span class="line">&#125;</span><br><span class="line">protected MultiNode addNode(Node node,MultiNode multiNode) &#123;</span><br><span class="line">	<span class="keyword">if</span>(node == null) &#123;</span><br><span class="line">		<span class="built_in">return</span> multiNode;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">else</span> <span class="keyword">if</span>(multiNode == null) &#123;</span><br><span class="line">		root = multiNode = new MultiNode();</span><br><span class="line">		multiNode.tail = multiNode.head = node;</span><br><span class="line">		multiNode.nodeCounter++;</span><br><span class="line">		<span class="built_in">return</span> multiNode;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">else</span>&#123;</span><br><span class="line">		Node head = multiNode.head;</span><br><span class="line">		<span class="keyword">do</span>&#123;</span><br><span class="line">			<span class="keyword">if</span>(head.num &gt; node.num) &#123;</span><br><span class="line">				<span class="keyword">if</span>(head.lesser!=null) &#123;</span><br><span class="line">					addNode(node,head.lesser);</span><br><span class="line">				&#125;</span><br><span class="line">				<span class="keyword">else</span> &#123;</span><br><span class="line">					<span class="keyword">if</span>(head.prev!=null) &#123;</span><br><span class="line">						<span class="keyword">if</span>(head.lesser != null) &#123;</span><br><span class="line">							node.greater = head.lesser;</span><br><span class="line">							head.lesser.lesserParent = node;</span><br><span class="line">						&#125;</span><br><span class="line">						<span class="keyword">if</span>(head.prev.greater!=null) &#123;</span><br><span class="line">							node.lesser = head.prev.greater;</span><br><span class="line">							head.prev.greater.greaterParent = node;</span><br><span class="line">						&#125;</span><br><span class="line">						head.prev.next = node;</span><br><span class="line">						node.prev = head.prev;</span><br><span class="line">					&#125;</span><br><span class="line">					<span class="keyword">else</span> &#123;</span><br><span class="line">						<span class="keyword">if</span>(head.lesser!=null) &#123;</span><br><span class="line">							node.greater = head.lesser;</span><br><span class="line">							head.lesser.lesserParent = node;</span><br><span class="line">						&#125;</span><br><span class="line">						multiNode.head = node;</span><br><span class="line">					&#125;</span><br><span class="line">					node.next = head;</span><br><span class="line">					head.prev = node;</span><br><span class="line">					<span class="keyword">if</span>(++multiNode.nodeCounter == multiNums) &#123;</span><br><span class="line">						Node breakNode = fissAndReturnBreakNode(multiNode,multiNums/2);</span><br><span class="line">						addNode(breakNode,multiNode.parent);</span><br><span class="line">					&#125;</span><br><span class="line">				&#125;</span><br><span class="line">				<span class="built_in">return</span> multiNode;</span><br><span class="line">			&#125;</span><br><span class="line">		&#125;<span class="keyword">while</span>((head = head.next)!=null);</span><br><span class="line">		</span><br><span class="line">		<span class="keyword">if</span>(multiNode.tail.greater!=null) &#123;</span><br><span class="line">			addNode(node,multiNode.tail.greater);</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">else</span> &#123;</span><br><span class="line">			multiNode.tail.next = node;</span><br><span class="line">			node.prev = multiNode.tail;</span><br><span class="line">			<span class="keyword">if</span>(multiNode.tail.greater!=null) &#123;</span><br><span class="line">				node.lesser = multiNode.tail.greater;</span><br><span class="line">				multiNode.tail.greater.greaterParent = node;</span><br><span class="line">			&#125;</span><br><span class="line">			multiNode.tail = node;</span><br><span class="line">			<span class="keyword">if</span>(++multiNode.nodeCounter == multiNums) &#123;</span><br><span class="line">				Node breakNode = fissAndReturnBreakNode(multiNode,multiNums/2);</span><br><span class="line">				addNode(breakNode,multiNode.parent);</span><br><span class="line">			&#125;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="built_in">return</span> multiNode;</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<h2 id="完整代码"><a href="#完整代码" class="headerlink" title="完整代码"></a>完整代码</h2><figure class="highlight bash"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br><span class="line">109</span><br><span class="line">110</span><br><span class="line">111</span><br><span class="line">112</span><br><span class="line">113</span><br><span class="line">114</span><br><span class="line">115</span><br><span class="line">116</span><br><span class="line">117</span><br><span class="line">118</span><br><span class="line">119</span><br><span class="line">120</span><br><span class="line">121</span><br><span class="line">122</span><br><span class="line">123</span><br><span class="line">124</span><br><span class="line">125</span><br><span class="line">126</span><br><span class="line">127</span><br><span class="line">128</span><br><span class="line">129</span><br><span class="line">130</span><br><span class="line">131</span><br><span class="line">132</span><br><span class="line">133</span><br><span class="line">134</span><br><span class="line">135</span><br><span class="line">136</span><br><span class="line">137</span><br><span class="line">138</span><br><span class="line">139</span><br><span class="line">140</span><br><span class="line">141</span><br><span class="line">142</span><br><span class="line">143</span><br><span class="line">144</span><br><span class="line">145</span><br><span class="line">146</span><br><span class="line">147</span><br><span class="line">148</span><br><span class="line">149</span><br><span class="line">150</span><br><span class="line">151</span><br><span class="line">152</span><br><span class="line">153</span><br><span class="line">154</span><br><span class="line">155</span><br><span class="line">156</span><br><span class="line">157</span><br><span class="line">158</span><br><span class="line">159</span><br><span class="line">160</span><br><span class="line">161</span><br><span class="line">162</span><br><span class="line">163</span><br><span class="line">164</span><br><span class="line">165</span><br><span class="line">166</span><br><span class="line">167</span><br><span class="line">168</span><br><span class="line">169</span><br><span class="line">170</span><br><span class="line">171</span><br></pre></td><td class="code"><pre><span class="line">package zcy;</span><br><span class="line"></span><br><span class="line">import java.util.concurrent.LinkedBlockingQueue;</span><br><span class="line"></span><br><span class="line">public class BTree &#123;</span><br><span class="line"></span><br><span class="line">	public BTree(int multiNums) &#123;</span><br><span class="line">		this.multiNums = multiNums;</span><br><span class="line">	&#125;</span><br><span class="line">	</span><br><span class="line">	volatile MultiNode root;//根节点</span><br><span class="line">	</span><br><span class="line">	int multiNums;//叉的数目</span><br><span class="line">	</span><br><span class="line">	public static void printTree(MultiNode node) &#123;</span><br><span class="line">		<span class="keyword">if</span>(node == null)</span><br><span class="line">			<span class="built_in">return</span>;</span><br><span class="line">		System.out.println(node+<span class="string">": "</span>);</span><br><span class="line">		LinkedBlockingQueue&lt;MultiNode&gt; queue = new LinkedBlockingQueue&lt;MultiNode&gt;();</span><br><span class="line">		Node head = node.head; </span><br><span class="line">		<span class="keyword">while</span>(head!=null) &#123;</span><br><span class="line">			<span class="keyword">if</span>(head.lesser!=null)</span><br><span class="line">				queue.add(head.lesser);</span><br><span class="line">			<span class="keyword">if</span>(head.greater!=null)</span><br><span class="line">				queue.add(head.greater);</span><br><span class="line">			System.out.println(head.num+<span class="string">" -&gt; lesser:"</span>+head.lesser+<span class="string">", -&gt;greate:"</span>+head.greater);</span><br><span class="line">			head = head.next;</span><br><span class="line">		&#125;</span><br><span class="line">		System.out.println();</span><br><span class="line">		queue.forEach(multiNode-&gt;printTree(multiNode));</span><br><span class="line">	&#125;</span><br><span class="line">	class MultiNode&#123;</span><br><span class="line">		int nodeCounter = 0;//数据节点总数</span><br><span class="line">		Node head;//数据节点链表头</span><br><span class="line">		Node tail;//数据节点链表尾</span><br><span class="line">		MultiNode parent;//父节点</span><br><span class="line">		Node greaterParent;//大父节点</span><br><span class="line">		Node lesserParent;//大父节点</span><br><span class="line">	&#125;</span><br><span class="line">	</span><br><span class="line">	class Node&#123;</span><br><span class="line">		int num;//索引大小</span><br><span class="line">		MultiNode greater;//大于</span><br><span class="line">		MultiNode lesser;//小于</span><br><span class="line">		Node prev;</span><br><span class="line">		Node next;</span><br><span class="line">	&#125;</span><br><span class="line">	</span><br><span class="line">	public void addNum(int num) &#123;</span><br><span class="line">		Node node = new Node();</span><br><span class="line">		node.num = num;</span><br><span class="line">		addNode(node,root);</span><br><span class="line">	&#125;</span><br><span class="line">	</span><br><span class="line">	private Node fissAndReturnBreakNode(MultiNode multiNode,int breakPoint) &#123;</span><br><span class="line">		<span class="keyword">if</span>(breakPoint&lt;1 || breakPoint&gt;=multiNums) &#123;</span><br><span class="line">			<span class="built_in">return</span> null;</span><br><span class="line">		&#125;</span><br><span class="line">		//裂变</span><br><span class="line">		<span class="keyword">if</span>(multiNode.greaterParent!=null) &#123;</span><br><span class="line">			//父节点断开</span><br><span class="line">			multiNode.greaterParent.lesser = null;</span><br><span class="line">			multiNode.greaterParent = null;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">if</span>(multiNode.lesserParent!=null) &#123;</span><br><span class="line">			//父节点断开</span><br><span class="line">			multiNode.lesserParent.greater = null;</span><br><span class="line">			multiNode.lesserParent = null;</span><br><span class="line">		&#125;</span><br><span class="line">		Node beakNode = multiNode.head;</span><br><span class="line">		<span class="keyword">for</span>(int i=0;i&lt;breakPoint;i++)</span><br><span class="line">			beakNode = beakNode.next;</span><br><span class="line">		MultiNode newMultiNode = new MultiNode();</span><br><span class="line">		newMultiNode.head = beakNode.next;</span><br><span class="line">		newMultiNode.tail = multiNode.tail;</span><br><span class="line">		multiNode.tail = beakNode.prev;</span><br><span class="line">		newMultiNode.nodeCounter = multiNode.nodeCounter - breakPoint -1;</span><br><span class="line">		multiNode.nodeCounter = breakPoint;</span><br><span class="line">		beakNode.next = beakNode.prev = newMultiNode.head.prev = multiNode.tail.next = null;</span><br><span class="line">		<span class="keyword">if</span>(beakNode.lesser!=null) &#123;</span><br><span class="line">			beakNode.lesser.lesserParent = multiNode.tail;</span><br><span class="line">			multiNode.tail.greater = beakNode.lesser;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">if</span>(beakNode.greater!=null) &#123;</span><br><span class="line">			beakNode.greater.greaterParent = newMultiNode.head;</span><br><span class="line">			newMultiNode.head.lesser = beakNode.greater;</span><br><span class="line">		&#125;</span><br><span class="line">		beakNode.lesser = multiNode;</span><br><span class="line">		multiNode.greaterParent = beakNode;</span><br><span class="line">		beakNode.greater = newMultiNode;</span><br><span class="line">		newMultiNode.lesserParent = beakNode;</span><br><span class="line">		newMultiNode.parent = multiNode.parent;</span><br><span class="line">		<span class="built_in">return</span> beakNode;</span><br><span class="line">	&#125;</span><br><span class="line">	</span><br><span class="line">	protected MultiNode addNode(Node node,MultiNode multiNode) &#123;</span><br><span class="line">		<span class="keyword">if</span>(node == null) &#123;</span><br><span class="line">			<span class="built_in">return</span> multiNode;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">else</span> <span class="keyword">if</span>(multiNode == null) &#123;</span><br><span class="line">			root = multiNode = new MultiNode();</span><br><span class="line">			multiNode.tail = multiNode.head = node;</span><br><span class="line">			multiNode.nodeCounter++;</span><br><span class="line">			<span class="built_in">return</span> multiNode;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">else</span>&#123;</span><br><span class="line">			Node head = multiNode.head;</span><br><span class="line">			<span class="keyword">do</span>&#123;</span><br><span class="line">				<span class="keyword">if</span>(head.num &gt; node.num) &#123;</span><br><span class="line">					<span class="keyword">if</span>(head.lesser!=null) &#123;</span><br><span class="line">						addNode(node,head.lesser);</span><br><span class="line">					&#125;</span><br><span class="line">					<span class="keyword">else</span> &#123;</span><br><span class="line">						<span class="keyword">if</span>(head.prev!=null) &#123;</span><br><span class="line">							<span class="keyword">if</span>(head.lesser != null) &#123;</span><br><span class="line">								node.greater = head.lesser;</span><br><span class="line">								head.lesser.lesserParent = node;</span><br><span class="line">							&#125;</span><br><span class="line">							<span class="keyword">if</span>(head.prev.greater!=null) &#123;</span><br><span class="line">								node.lesser = head.prev.greater;</span><br><span class="line">								head.prev.greater.greaterParent = node;</span><br><span class="line">							&#125;</span><br><span class="line">							head.prev.next = node;</span><br><span class="line">							node.prev = head.prev;</span><br><span class="line">						&#125;</span><br><span class="line">						<span class="keyword">else</span> &#123;</span><br><span class="line">							<span class="keyword">if</span>(head.lesser!=null) &#123;</span><br><span class="line">								node.greater = head.lesser;</span><br><span class="line">								head.lesser.lesserParent = node;</span><br><span class="line">							&#125;</span><br><span class="line">							multiNode.head = node;</span><br><span class="line">						&#125;</span><br><span class="line">						node.next = head;</span><br><span class="line">						head.prev = node;</span><br><span class="line">						<span class="keyword">if</span>(++multiNode.nodeCounter == multiNums) &#123;</span><br><span class="line">							Node breakNode = fissAndReturnBreakNode(multiNode,multiNums/2);</span><br><span class="line">							addNode(breakNode,multiNode.parent);</span><br><span class="line">						&#125;</span><br><span class="line">					&#125;</span><br><span class="line">					<span class="built_in">return</span> multiNode;</span><br><span class="line">				&#125;</span><br><span class="line">			&#125;<span class="keyword">while</span>((head = head.next)!=null);</span><br><span class="line">			</span><br><span class="line">			<span class="keyword">if</span>(multiNode.tail.greater!=null) &#123;</span><br><span class="line">				addNode(node,multiNode.tail.greater);</span><br><span class="line">			&#125;</span><br><span class="line">			<span class="keyword">else</span> &#123;</span><br><span class="line">				multiNode.tail.next = node;</span><br><span class="line">				node.prev = multiNode.tail;</span><br><span class="line">				<span class="keyword">if</span>(multiNode.tail.greater!=null) &#123;</span><br><span class="line">					node.lesser = multiNode.tail.greater;</span><br><span class="line">					multiNode.tail.greater.greaterParent = node;</span><br><span class="line">				&#125;</span><br><span class="line">				multiNode.tail = node;</span><br><span class="line">				<span class="keyword">if</span>(++multiNode.nodeCounter == multiNums) &#123;</span><br><span class="line">					Node breakNode = fissAndReturnBreakNode(multiNode,multiNums/2);</span><br><span class="line">					addNode(breakNode,multiNode.parent);</span><br><span class="line">				&#125;</span><br><span class="line">			&#125;</span><br><span class="line">			<span class="built_in">return</span> multiNode;</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	</span><br><span class="line">	public static void main(String[] args) &#123;</span><br><span class="line">		BTree tree = new BTree(4);//4叉B树每个multi最多含有3个节点</span><br><span class="line">		<span class="keyword">for</span>(int i=0;i&lt;7;i++)</span><br><span class="line">			tree.addNum(i);</span><br><span class="line">		BTree.printTree(tree.root);</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h3 id="请移步"><a href="#请移步" class="headerlink" title="请移步"></a>请移步</h3><p>个人主页: <a href="http://yangyitao.top" target="_blank" rel="noopener">yangyitao.top</a></p>

      
    </div>
    
    <div class="article-info article-info-index">
      
      
      

      
      <div class="clearfix"></div>
    </div>
      
    
  </div>
  
</article>







  
    <article id="post-手撕AVL树" class="article article-type-post" itemscope itemprop="blogPost">
  
    <div class="article-meta">
      <a href="/blog/2019/03/31/手撕AVL树/" class="article-date">
  	<time datetime="2019-03-31T08:30:48.042Z" itemprop="datePublished">2019-03-31</time>
</a>
    </div>
  
  <div class="article-inner">
    
      <input type="hidden" class="isFancy" />
    
    
      <header class="article-header">
        
  
    <h1 itemprop="name">
      <a class="article-title" href="/blog/2019/03/31/手撕AVL树/">
        手撕AVL树
        
      </a>
    </h1>
  

      </header>
      
    
    <div class="article-entry" itemprop="articleBody">
      
        <p>欢迎查看Eetal的第十五篇博客–手撕AVL树</p>
<h2 id="BST"><a href="#BST" class="headerlink" title="BST"></a>BST</h2><p>BINARY SEARCH TREE二叉查找树，代表树中节点为有序存储<br>所有节点都相同满足以下条件之一<br>1.左子节点值大于等于根节点值且右子节点值小于根节点值<br>2.左子节点值小于等于根节点值且右子节点值大于根节点值<br>的二叉树即位二叉查找树<br>AVL average BST 是一棵平衡的二叉查找树，通过平衡使得单次查找的时间复杂度不会超过logn</p>
<h2 id="AVL-Tree"><a href="#AVL-Tree" class="headerlink" title="AVL Tree"></a>AVL Tree</h2><p>平衡树的特点是，任意一个节点，其左子树的高度与右子树的高度差保持在1以内（包括1）<br>当出现高度差超过1的子树则进行旋转来调整，旋转时不破坏有序</p>
<h2 id="旋转"><a href="#旋转" class="headerlink" title="旋转"></a>旋转</h2><h3 id="右旋转"><a href="#右旋转" class="headerlink" title="右旋转"></a>右旋转</h3><p>假设左边过高（一般这种过高表现为高度差为2，因为我们应在每次进行插入和删除时旋转进行维护，所以不会出现高度差为3的情况）<br><img src="/blog/images/avl-tree/r-normal.jpg" alt="普通右旋"><br>这时我们通过这种右旋转可以把左边过高子树的一个节点提上来，使得左子树节点高度-1，右子树节点高度+1<br>伪代码就是<br>parent = 要旋转的节点<br>将parent的左节点断开，再将断开的左节点的右子树断开，重新接到parent，作为parent新的左子树<br>将parent从他父亲断开，将parent作为他原来的左子节点（被断开的左子节点）的右子树<br>最后将parent原来的父亲作为此时parent新的父节点（原来的左子节点）的父亲（就是交换位置）</p>
<p>代码实现<br><figure class="highlight bash"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br></pre></td><td class="code"><pre><span class="line">public Node rightTransformAndReturn(Node node) &#123;</span><br><span class="line">	System.out.println(<span class="string">"right transform"</span>);</span><br><span class="line">	Node left = node.leftChild;</span><br><span class="line">	Node leftRightChild = left.rightChild;</span><br><span class="line">	<span class="keyword">if</span>(leftRightChild!=null) &#123;</span><br><span class="line">		leftRightChild.parent = node;</span><br><span class="line">		leftRightChild.status = LEFTSTATUS;</span><br><span class="line">	&#125;</span><br><span class="line">	node.leftChild = leftRightChild;</span><br><span class="line">	left.rightChild = node;</span><br><span class="line">	left.parent = node.parent;</span><br><span class="line">	node.parent = left;</span><br><span class="line">	left.status = node.status;</span><br><span class="line">	<span class="keyword">if</span>(node.status == LEFTSTATUS) &#123;</span><br><span class="line">		left.parent.leftChild = left;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">else</span> <span class="keyword">if</span>(node.status == RIGHTSTATUS)&#123;</span><br><span class="line">		left.parent.rightChild = left;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">else</span> &#123;</span><br><span class="line">		root = left;</span><br><span class="line">	&#125;</span><br><span class="line">	node.status = RIGHTSTATUS;</span><br><span class="line">	<span class="keyword">while</span>(node!=null) &#123;</span><br><span class="line">		node.height = Math.max(getHeight(node.leftChild)+1, getHeight(node.rightChild)+1);</span><br><span class="line">		node = node.parent;</span><br><span class="line">	&#125;</span><br><span class="line">	node = left;</span><br><span class="line">	<span class="built_in">return</span> node;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<p>上面只分析了第一种情况，有时左子树会是这样<br><img src="/blog/images/avl-tree/r2.jpg" alt="特殊右旋"><br>这时如果按照第一种的做法，此时最终结果会使得右子树高于左子树导致不平衡<br>原因是第一步里有 这一步</p>
<h5 id="将parent的左节点断开，再将断开的左节点的右子树断开，重新接到parent，作为parent新的左子树"><a href="#将parent的左节点断开，再将断开的左节点的右子树断开，重新接到parent，作为parent新的左子树" class="headerlink" title="将parent的左节点断开，再将断开的左节点的右子树断开，重新接到parent，作为parent新的左子树"></a>将parent的左节点断开，再将断开的左节点的右子树断开，重新接到parent，作为parent新的左子树</h5><p>这一步是为了保证其有序不被破坏，所以从断开的是其左节点的右子树，也就是这颗右子树高度是不变的<br>而后右子树又会链接到parent，如果导致树高的不平衡是这颗右子树造成，则旋转后其仍是不平衡的（因为左边减少的高度1实际是左子树的高度）</p>
<p>于是我们得想办法把他变回第一种情况，做法就是，先使用左旋转其parent的左子树，将其变为下图<br><img src="/blog/images/avl-tree/r3.jpg" alt="特殊右旋"><br>这时就可以使用第一种情况的方法来应对了<br>至于为什么只要一次右旋转因为一开始我们就讲过，高度差不会超过2，那平衡的子树的左右结点高度差就不会超过1</p>
<h3 id="左旋转"><a href="#左旋转" class="headerlink" title="左旋转"></a>左旋转</h3><p>此处就是右旋转的镜像实现，就不过多阐述</p>
<figure class="highlight bash"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br></pre></td><td class="code"><pre><span class="line">public Node leftTransformAndReturn(Node node) &#123;</span><br><span class="line">	System.out.println(<span class="string">"left transform"</span>);</span><br><span class="line">	Node right = node.rightChild;</span><br><span class="line">	Node rightLeftChild = right.leftChild;</span><br><span class="line">	<span class="keyword">if</span>(rightLeftChild!=null) &#123;</span><br><span class="line">		rightLeftChild.parent = node;</span><br><span class="line">		rightLeftChild.status = RIGHTSTATUS;</span><br><span class="line">	&#125;</span><br><span class="line">	node.rightChild = rightLeftChild;</span><br><span class="line">	right.leftChild = node;</span><br><span class="line">	right.parent = node.parent;</span><br><span class="line">	node.parent = right;</span><br><span class="line">	right.status = node.status;</span><br><span class="line">	<span class="keyword">if</span>(node.status == LEFTSTATUS) &#123;</span><br><span class="line">		right.parent.leftChild = right;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">else</span> <span class="keyword">if</span>(node.status == RIGHTSTATUS)&#123;</span><br><span class="line">		right.parent.rightChild = right;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">else</span> &#123;</span><br><span class="line">		root = right;</span><br><span class="line">	&#125;</span><br><span class="line">	node.status = LEFTSTATUS;</span><br><span class="line">	<span class="keyword">while</span>(node!=null) &#123;</span><br><span class="line">		node.height = Math.max(getHeight(node.leftChild)+1, getHeight(node.rightChild)+1);</span><br><span class="line">		node = node.parent;</span><br><span class="line">	&#125;</span><br><span class="line">	node = right;</span><br><span class="line">	<span class="built_in">return</span> node;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h3 id="最终代码"><a href="#最终代码" class="headerlink" title="最终代码"></a>最终代码</h3><p>我们将上方阐述的特殊情况（左旋转的可以联想都是对应的）总结，把对于两种情况的处理都封装<br>使用递归实现<br><figure class="highlight bash"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br><span class="line">109</span><br><span class="line">110</span><br><span class="line">111</span><br><span class="line">112</span><br><span class="line">113</span><br><span class="line">114</span><br><span class="line">115</span><br><span class="line">116</span><br><span class="line">117</span><br><span class="line">118</span><br><span class="line">119</span><br><span class="line">120</span><br><span class="line">121</span><br><span class="line">122</span><br><span class="line">123</span><br><span class="line">124</span><br><span class="line">125</span><br><span class="line">126</span><br><span class="line">127</span><br><span class="line">128</span><br><span class="line">129</span><br><span class="line">130</span><br><span class="line">131</span><br><span class="line">132</span><br><span class="line">133</span><br><span class="line">134</span><br><span class="line">135</span><br><span class="line">136</span><br><span class="line">137</span><br><span class="line">138</span><br><span class="line">139</span><br><span class="line">140</span><br><span class="line">141</span><br><span class="line">142</span><br><span class="line">143</span><br><span class="line">144</span><br><span class="line">145</span><br><span class="line">146</span><br><span class="line">147</span><br><span class="line">148</span><br><span class="line">149</span><br><span class="line">150</span><br><span class="line">151</span><br><span class="line">152</span><br><span class="line">153</span><br><span class="line">154</span><br><span class="line">155</span><br><span class="line">156</span><br><span class="line">157</span><br><span class="line">158</span><br><span class="line">159</span><br><span class="line">160</span><br><span class="line">161</span><br><span class="line">162</span><br><span class="line">163</span><br><span class="line">164</span><br><span class="line">165</span><br><span class="line">166</span><br><span class="line">167</span><br><span class="line">168</span><br><span class="line">169</span><br><span class="line">170</span><br><span class="line">171</span><br><span class="line">172</span><br><span class="line">173</span><br><span class="line">174</span><br><span class="line">175</span><br><span class="line">176</span><br><span class="line">177</span><br><span class="line">178</span><br><span class="line">179</span><br><span class="line">180</span><br><span class="line">181</span><br><span class="line">182</span><br><span class="line">183</span><br><span class="line">184</span><br><span class="line">185</span><br><span class="line">186</span><br><span class="line">187</span><br><span class="line">188</span><br><span class="line">189</span><br><span class="line">190</span><br><span class="line">191</span><br><span class="line">192</span><br><span class="line">193</span><br><span class="line">194</span><br><span class="line">195</span><br><span class="line">196</span><br><span class="line">197</span><br><span class="line">198</span><br></pre></td><td class="code"><pre><span class="line"></span><br><span class="line">public class AVLTree &#123;</span><br><span class="line"></span><br><span class="line">	Node root;</span><br><span class="line">	static final int LEFTSTATUS = 0;</span><br><span class="line">	static final int RIGHTSTATUS = 1;</span><br><span class="line"></span><br><span class="line">	static class Node&#123;</span><br><span class="line">		int num;</span><br><span class="line">		Node leftChild;</span><br><span class="line">		Node rightChild;</span><br><span class="line">		Node parent;</span><br><span class="line">		int height = 0;</span><br><span class="line">		int status = -1;//root</span><br><span class="line">		@Override</span><br><span class="line">		public String <span class="function"><span class="title">toString</span></span>() &#123;</span><br><span class="line">			<span class="built_in">return</span> num+<span class="string">",height["</span>+height+<span class="string">"]-&gt;left["</span>+(leftChild==null?<span class="string">"null"</span>:leftChild.num)+<span class="string">"],-&gt;right["</span>+(rightChild==null?<span class="string">"null"</span>:rightChild.num)+<span class="string">"]"</span>;</span><br><span class="line">		&#125;</span><br><span class="line">		</span><br><span class="line">	&#125;</span><br><span class="line">	public void printTree(Node parent) &#123;</span><br><span class="line">		<span class="keyword">if</span>(parent!=null) &#123;</span><br><span class="line">			System.out.println(parent);</span><br><span class="line">			printTree(parent.leftChild);</span><br><span class="line">			printTree(parent.rightChild);</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	//注意，左旋右旋会改变原来的父节点位置的节点(包括root)</span><br><span class="line">	public Node leftTransformAndReturn(Node node) &#123;</span><br><span class="line">		System.out.println(<span class="string">"left transform"</span>);</span><br><span class="line">		Node right = node.rightChild;</span><br><span class="line">		//双旋转</span><br><span class="line">		<span class="keyword">if</span>(getHeight(right.leftChild)&gt;getHeight(right.rightChild)) &#123;</span><br><span class="line">			rightTransformAndReturn(right);</span><br><span class="line">		&#125;</span><br><span class="line">		Node rightLeftChild = right.leftChild;</span><br><span class="line">		<span class="keyword">if</span>(rightLeftChild!=null) &#123;</span><br><span class="line">			rightLeftChild.parent = node;</span><br><span class="line">			rightLeftChild.status = RIGHTSTATUS;</span><br><span class="line">		&#125;</span><br><span class="line">		node.rightChild = rightLeftChild;</span><br><span class="line">		right.leftChild = node;</span><br><span class="line">		right.parent = node.parent;</span><br><span class="line">		node.parent = right;</span><br><span class="line">		right.status = node.status;</span><br><span class="line">		<span class="keyword">if</span>(node.status == LEFTSTATUS) &#123;</span><br><span class="line">			right.parent.leftChild = right;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">else</span> <span class="keyword">if</span>(node.status == RIGHTSTATUS)&#123;</span><br><span class="line">			right.parent.rightChild = right;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">else</span> &#123;</span><br><span class="line">			root = right;</span><br><span class="line">		&#125;</span><br><span class="line">		node.status = LEFTSTATUS;</span><br><span class="line">		<span class="keyword">while</span>(node!=null) &#123;</span><br><span class="line">			node.height = Math.max(getHeight(node.leftChild)+1, getHeight(node.rightChild)+1);</span><br><span class="line">			node = node.parent;</span><br><span class="line">		&#125;</span><br><span class="line">		node = right;</span><br><span class="line">		<span class="built_in">return</span> node;</span><br><span class="line">	&#125;</span><br><span class="line">	public Node rightTransformAndReturn(Node node) &#123;</span><br><span class="line">		System.out.println(<span class="string">"right transform"</span>);</span><br><span class="line">		Node left = node.leftChild;</span><br><span class="line">		//双旋转</span><br><span class="line">		<span class="keyword">if</span>(getHeight(left.rightChild)&gt;getHeight(left.leftChild)) &#123;</span><br><span class="line">			leftTransformAndReturn(left);</span><br><span class="line">		&#125;</span><br><span class="line">		Node leftRightChild = left.rightChild;</span><br><span class="line">		<span class="keyword">if</span>(leftRightChild!=null) &#123;</span><br><span class="line">			leftRightChild.parent = node;</span><br><span class="line">			leftRightChild.status = LEFTSTATUS;</span><br><span class="line">		&#125;</span><br><span class="line">		node.leftChild = leftRightChild;</span><br><span class="line">		left.rightChild = node;</span><br><span class="line">		left.parent = node.parent;</span><br><span class="line">		node.parent = left;</span><br><span class="line">		left.status = node.status;</span><br><span class="line">		<span class="keyword">if</span>(node.status == LEFTSTATUS) &#123;</span><br><span class="line">			left.parent.leftChild = left;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">else</span> <span class="keyword">if</span>(node.status == RIGHTSTATUS)&#123;</span><br><span class="line">			left.parent.rightChild = left;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">else</span> &#123;</span><br><span class="line">			root = left;</span><br><span class="line">		&#125;</span><br><span class="line">		node.status = RIGHTSTATUS;</span><br><span class="line">		<span class="keyword">while</span>(node!=null) &#123;</span><br><span class="line">			node.height = Math.max(getHeight(node.leftChild)+1, getHeight(node.rightChild)+1);</span><br><span class="line">			node = node.parent;</span><br><span class="line">		&#125;</span><br><span class="line">		node = left;</span><br><span class="line">		<span class="built_in">return</span> node;</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">	public int getHeight(Node node) &#123;</span><br><span class="line">		//获得树高，null为-1</span><br><span class="line">		<span class="built_in">return</span> node == null ? -1 : node.height;</span><br><span class="line">	&#125;</span><br><span class="line">	public int getBF(Node node) &#123;</span><br><span class="line">		//获得平衡因子---左子树高-右子树高</span><br><span class="line">		<span class="built_in">return</span>  getHeight(node.leftChild)- getHeight(node.rightChild);</span><br><span class="line">	&#125;</span><br><span class="line">	public void avl(Node parent) &#123;</span><br><span class="line">		<span class="keyword">if</span>(parent == null) &#123;</span><br><span class="line">			<span class="built_in">return</span>;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">else</span> &#123;</span><br><span class="line">			Node left = parent.leftChild;</span><br><span class="line">			Node right = parent.rightChild;</span><br><span class="line">			<span class="keyword">if</span>(getHeight(right)&gt;getHeight(left)+1) &#123;</span><br><span class="line">				leftTransformAndReturn(parent);</span><br><span class="line">			&#125;</span><br><span class="line">			<span class="keyword">else</span> <span class="keyword">if</span>(getHeight(left)&gt;getHeight(right)+1) &#123;</span><br><span class="line">				rightTransformAndReturn(parent);</span><br><span class="line">			&#125;</span><br><span class="line">			<span class="keyword">else</span> &#123;</span><br><span class="line">				avl(parent.parent);</span><br><span class="line">			&#125;</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	public Node addAndReturnParent(Node node,Node parent) &#123;</span><br><span class="line">		<span class="keyword">if</span>(parent == null) &#123;</span><br><span class="line">			root = parent = node;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">else</span> &#123;</span><br><span class="line">			<span class="keyword">if</span>(parent.num&gt;node.num) &#123;</span><br><span class="line">				//right add</span><br><span class="line">				Node right = parent.rightChild;</span><br><span class="line">				<span class="keyword">if</span>(right == null) &#123;</span><br><span class="line">					node.parent = parent;</span><br><span class="line">					node.status = RIGHTSTATUS;</span><br><span class="line">					parent.rightChild = node;</span><br><span class="line">					<span class="keyword">if</span>(parent.leftChild == null) &#123;</span><br><span class="line">						Node temp = parent;</span><br><span class="line">						temp.height++;</span><br><span class="line">						boolean flag = <span class="literal">true</span>;</span><br><span class="line">						<span class="keyword">while</span>((temp=temp.parent)!=null &amp;&amp; flag) &#123;</span><br><span class="line">							int oldHeight = temp.height;</span><br><span class="line">							temp.height = Math.max(getHeight(temp.leftChild)+1, getHeight(temp.rightChild)+1);</span><br><span class="line">							flag = (oldHeight != temp.height);</span><br><span class="line">						&#125;</span><br><span class="line">						avl(parent);</span><br><span class="line">					&#125;</span><br><span class="line">				&#125;</span><br><span class="line">				<span class="keyword">else</span> &#123;</span><br><span class="line">					addAndReturnParent(node,right);</span><br><span class="line">				&#125;</span><br><span class="line">			&#125;</span><br><span class="line">			<span class="keyword">else</span> &#123;</span><br><span class="line">				//left add</span><br><span class="line">				Node left = parent.leftChild;</span><br><span class="line">				<span class="keyword">if</span>(left == null) &#123;</span><br><span class="line">					node.parent = parent;</span><br><span class="line">					parent.leftChild = node;</span><br><span class="line">					node.status = LEFTSTATUS;</span><br><span class="line">					<span class="keyword">if</span>(parent.rightChild == null) &#123;</span><br><span class="line">						Node temp = parent;</span><br><span class="line">						temp.height++;</span><br><span class="line">						boolean flag = <span class="literal">true</span>;</span><br><span class="line">						<span class="keyword">while</span>((temp=temp.parent)!=null &amp;&amp; flag) &#123;</span><br><span class="line">							int oldHeight = temp.height;</span><br><span class="line">							temp.height = Math.max(getHeight(temp.leftChild)+1, getHeight(temp.rightChild)+1);</span><br><span class="line">							flag = (oldHeight != temp.height);</span><br><span class="line">						&#125;</span><br><span class="line">						avl(parent);</span><br><span class="line">					&#125;</span><br><span class="line">				&#125;</span><br><span class="line">				<span class="keyword">else</span> &#123;</span><br><span class="line">					addAndReturnParent(node,left);</span><br><span class="line">				&#125;</span><br><span class="line">			&#125;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="built_in">return</span> parent;</span><br><span class="line">	&#125;</span><br><span class="line">	public Node addNum(int num) &#123;</span><br><span class="line">		Node node = new Node();</span><br><span class="line">		node.num = num;</span><br><span class="line">		addAndReturnParent(node, root);</span><br><span class="line">		<span class="built_in">return</span> node;</span><br><span class="line">	&#125;</span><br><span class="line">	</span><br><span class="line">	public Node findNum(int num) &#123;</span><br><span class="line">		Node node = root;</span><br><span class="line">		<span class="keyword">while</span>(node!=null) &#123;</span><br><span class="line">			<span class="keyword">if</span>(node.num == num)</span><br><span class="line">				<span class="built_in">break</span>;</span><br><span class="line">			<span class="keyword">else</span> <span class="keyword">if</span>(node.num&lt;num)</span><br><span class="line">				node = node.leftChild;</span><br><span class="line">			<span class="keyword">else</span></span><br><span class="line">				node = node.rightChild;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="built_in">return</span> node;</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<h3 id="节点删除"><a href="#节点删除" class="headerlink" title="节点删除"></a>节点删除</h3><p>如果要删除节点，此时第一考虑树高，<br>1.如果是叶子节点我们可以直接删除，并调整树<br>2.不是叶子节点，找出一个作为替代的叶子节点，顶替其位置（只需要交换值），把问题变为第一种情况</p>
<p>具体的顶替查找就是，如果其左子树为空则左旋一次，变为叶子节点<br>如果右子树为空则右旋一次，变为叶子结点<br>如果都不为空，根据左右子树高度判断，<br>从高度大的一方查找替代后能保持有序的叶子节点（此处判断主要是为了优化减少旋转的次数，不判断选择一边也不影响，因为最终都会调整）<br>最后删除叶子节点后递归调整树</p>
<p>代码实现<br><figure class="highlight bash"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br></pre></td><td class="code"><pre><span class="line">public Node deleteNode(Node node) &#123;</span><br><span class="line">		System.out.println(<span class="string">"delete Node...:"</span>+node);</span><br><span class="line">		<span class="keyword">if</span>(node == null)</span><br><span class="line">			<span class="built_in">return</span> node;</span><br><span class="line">		<span class="keyword">if</span>(getHeight(node)==0) &#123;</span><br><span class="line">			Node parent = node.parent;</span><br><span class="line">			node.parent = null;</span><br><span class="line">			<span class="keyword">if</span>(node == root) &#123;</span><br><span class="line">				root = null;</span><br><span class="line">			&#125;</span><br><span class="line">			<span class="keyword">else</span> <span class="keyword">if</span>(node.status == LEFTSTATUS) &#123;</span><br><span class="line">				parent.leftChild = null;</span><br><span class="line">				Node temp = parent;</span><br><span class="line">				boolean flag = <span class="literal">true</span>;</span><br><span class="line">				<span class="keyword">while</span>((temp=temp.parent)!=null &amp;&amp; flag) &#123;</span><br><span class="line">					int oldHeight = temp.height;</span><br><span class="line">					temp.height = Math.max(getHeight(temp.leftChild)+1, getHeight(temp.rightChild)+1);</span><br><span class="line">					flag = (oldHeight != temp.height);</span><br><span class="line">				&#125;</span><br><span class="line">				avl(parent);</span><br><span class="line"></span><br><span class="line">			&#125;</span><br><span class="line">			<span class="keyword">else</span> &#123;</span><br><span class="line">				parent.rightChild = null;</span><br><span class="line">				Node temp = parent;</span><br><span class="line">				boolean flag = <span class="literal">true</span>;</span><br><span class="line">				<span class="keyword">while</span>((temp=temp.parent)!=null &amp;&amp; flag) &#123;</span><br><span class="line">					int oldHeight = temp.height;</span><br><span class="line">					temp.height = Math.max(getHeight(temp.leftChild)+1, getHeight(temp.rightChild)+1);</span><br><span class="line">					flag = (oldHeight != temp.height);</span><br><span class="line">				&#125;</span><br><span class="line">				avl(parent);</span><br><span class="line">			&#125;</span><br><span class="line">			</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">else</span> &#123;</span><br><span class="line">			<span class="keyword">if</span>(node.leftChild == null) &#123;</span><br><span class="line">				leftTransformAndReturn(node);</span><br><span class="line">				deleteNode(node);</span><br><span class="line">			&#125;</span><br><span class="line">			<span class="keyword">else</span> <span class="keyword">if</span>(node.rightChild == null) &#123;</span><br><span class="line">				rightTransformAndReturn(node);</span><br><span class="line">				deleteNode(node);</span><br><span class="line">			&#125;</span><br><span class="line">			<span class="keyword">else</span> <span class="keyword">if</span>(getHeight(node.leftChild)&gt;getHeight(node.rightChild)) &#123;</span><br><span class="line">				Node leftSmall = node.leftChild;</span><br><span class="line">				<span class="keyword">while</span>(leftSmall.rightChild!=null) &#123;</span><br><span class="line">					leftSmall = leftSmall.rightChild;</span><br><span class="line">				&#125;</span><br><span class="line">				node.num ^= leftSmall.num;</span><br><span class="line">				leftSmall.num ^= node.num;</span><br><span class="line">				node.num ^= leftSmall.num;</span><br><span class="line">				deleteNode(leftSmall);</span><br><span class="line">			&#125;</span><br><span class="line">			<span class="keyword">else</span> &#123;</span><br><span class="line">				Node rightBig = node.rightChild;</span><br><span class="line">				<span class="keyword">while</span>(rightBig.leftChild!=null) &#123;</span><br><span class="line">					rightBig = rightBig.leftChild;</span><br><span class="line">				&#125;</span><br><span class="line">				node.num ^= rightBig.num;</span><br><span class="line">				rightBig.num ^= node.num;</span><br><span class="line">				node.num ^= rightBig.num;</span><br><span class="line">				deleteNode(rightBig);</span><br><span class="line">			&#125;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="built_in">return</span> node;</span><br><span class="line">	&#125;</span><br><span class="line">	public Node deleteNum(int num) &#123;</span><br><span class="line">		Node node = findNum(num);</span><br><span class="line">		<span class="built_in">return</span> deleteNode(node);</span><br><span class="line">	&#125;</span><br></pre></td></tr></table></figure></p>
<h3 id="请移步"><a href="#请移步" class="headerlink" title="请移步"></a>请移步</h3><p>个人主页: <a href="http://yangyitao.top" target="_blank" rel="noopener">yangyitao.top</a></p>

      
    </div>
    
    <div class="article-info article-info-index">
      
      
      

      
      <div class="clearfix"></div>
    </div>
      
    
  </div>
  
</article>







  
    <article id="post-java的四种引用类型" class="article article-type-post" itemscope itemprop="blogPost">
  
    <div class="article-meta">
      <a href="/blog/2019/03/30/java的四种引用类型/" class="article-date">
  	<time datetime="2019-03-30T08:36:49.177Z" itemprop="datePublished">2019-03-30</time>
</a>
    </div>
  
  <div class="article-inner">
    
      <input type="hidden" class="isFancy" />
    
    
      <header class="article-header">
        
  
    <h1 itemprop="name">
      <a class="article-title" href="/blog/2019/03/30/java的四种引用类型/">
        java的四种引用类型
        
      </a>
    </h1>
  

      </header>
      
    
    <div class="article-entry" itemprop="articleBody">
      
        <p>欢迎查看Eetal的第十四篇博客–java的四种引用类型</p>
<h2 id="引用队列"><a href="#引用队列" class="headerlink" title="引用队列"></a>引用队列</h2><p>ReferenceQueue,引用队列内部维护一个Lock锁，除了强引用，其他类型引用都包含一个可以传入引用队列的构造函数<br>引用的对象在即将被回收时，会把绑定了引用队列的引用加入引用队列<br>然后回收该对象，因为这时其会变为InActive（死亡 ）</p>
<h2 id="Reference抽象类"><a href="#Reference抽象类" class="headerlink" title="Reference抽象类"></a>Reference抽象类</h2><figure class="highlight bash"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br></pre></td><td class="code"><pre><span class="line">   /*引用实例处于四种可能的内部状态之一：</span><br><span class="line">*</span><br><span class="line">*活性：由垃圾收集器进行特殊处理。一些</span><br><span class="line">*收集器检测到referent已更改为适当的状态，</span><br><span class="line">*它将更改实例的状态为挂起或不活动，具体取决于实例是否在队列中注册已创建。</span><br><span class="line">*在前一种情况下，它还将实例添加到挂起的引用列表。</span><br><span class="line">*新创建的实例处于活动状态。</span><br><span class="line">*</span><br><span class="line">*挂起：挂起引用列表的元素，等待被引用处理程序线程排队。</span><br><span class="line">*未注册的实例从未处于这种状态。</span><br><span class="line">*</span><br><span class="line">*排队：处于等待加入引用队列的等待队列，（因为加入引用队列的方法需要获取锁）</span><br><span class="line">*</span><br><span class="line">*不活动：没什么可做的。一旦一个实例变为非活动状态，状态永远不会改变。</span><br><span class="line">*</span><br><span class="line">*状态在队列和下一个字段中编码如下：</span><br><span class="line">*</span><br><span class="line">*active:queue=referencequeue，注册实例，</span><br><span class="line">*或referencequeue.null，如果它未注册到队列；</span><br><span class="line">*next=NULL。</span><br><span class="line">*</span><br><span class="line">*挂起：queue=referencequeue，实例已注册；</span><br><span class="line">*next=this</span><br><span class="line">*</span><br><span class="line">*排队：queue=referencequeue.enqueued；</span><br><span class="line">*next=following instance</span><br><span class="line">*在队列中，或者在列表的末尾。</span><br><span class="line">*</span><br><span class="line">*非活动：queue=referencequeue.null；</span><br><span class="line">*next=this。</span><br><span class="line">*</span><br><span class="line">*使用此方案，收集器只需按顺序检查下一个字段确定引用实例是否需要特殊处理：如果下一个字段为空，则实例处于活动状态；</span><br><span class="line">*如果为非空，收集器应该正常处理该实例。</span><br><span class="line">*确保并发收集器可以发现活动引用不干扰可能应用的应用程序线程的对象enqueue（）方法到这些对象，</span><br><span class="line">*收集器应链接通过发现的字段发现的对象。发现的字段还用于链接挂起列表中的引用对象。</span><br><span class="line">*/</span><br><span class="line"></span><br><span class="line">Reference(T referent, ReferenceQueue&lt;? super T&gt; queue) &#123;</span><br><span class="line">	this.referent = referent;</span><br><span class="line">	this.queue = (queue == null) ? ReferenceQueue.NULL : queue;</span><br><span class="line">&#125;</span><br><span class="line">private T referent;         /* Treated specially by GC */</span><br><span class="line"></span><br><span class="line">volatile ReferenceQueue&lt;? super T&gt; queue;</span><br></pre></td></tr></table></figure>
<p>网上大部分博客对于四种引用的说法都不准确，不去关心为何垃圾回收时会将对应引用加入对应引用队列<br>这里留意抽象类里的注释Treated specially by GC(被gc特殊对待)<br>具体过程就是，当满足了该引用对象被回收的条件时（在没有强引用引用他的前提下）<br>将该引用加入引用队列，并且该引用队列不再引用该对象（清除，注意虚引用在此处不同，虚引用需要等到对象上所有的引用清除以后才清除）<br>同时该对象也会变为死亡状态，会被垃圾回收器回收<br>接下来讲讲各个引用的条件</p>
<h2 id="强引用"><a href="#强引用" class="headerlink" title="强引用"></a>强引用</h2><p>没什么好说的<br>java默认的引用类型，就是强引用类型<br>比如<br>Object o;<br>这就是一个强引用，只是没有引用对象</p>
<h2 id="软引用"><a href="#软引用" class="headerlink" title="软引用"></a>软引用</h2><p>被软引用的对象在垃圾回收器线程扫描到且当jvm内存不足时，该软引用就会不再引用该对象<br>软引用可以与引用队列搭配使用<br>使用方式（传递对象）</p>
<p>SoftReference<object> sr = new SoftReference<object>(new Object());<br>sr.get(); //返回软引用对象，此处为Object类型</object></object></p>
<h2 id="弱引用"><a href="#弱引用" class="headerlink" title="弱引用"></a>弱引用</h2><p>被弱引用的对象在垃圾回收器线程扫描到时，该弱引用就会不再引用该对象<br>弱引用可以与引用队列搭配使用</p>
<p>WeakReference<object> wr = new WeakReference<object>(new Object());<br>wr.get(); //返回弱引用对象，此处为Object类型</object></object></p>
<h2 id="虚引用"><a href="#虚引用" class="headerlink" title="虚引用"></a>虚引用</h2><p>虚引用并不影响对象的生命周期<br>虚引用必须与引用队列搭配使用<br>虚引用并不可访问引用对象，get总是返回null<br>虚引用需要等到对象上所有的引用清除以后才清除<br><figure class="highlight bash"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br></pre></td><td class="code"><pre><span class="line">public class PhantomReference&lt;T&gt; extends Reference&lt;T&gt; &#123;</span><br><span class="line"></span><br><span class="line">	/**</span><br><span class="line">	 * Returns this reference object<span class="string">'s referent.  Because the referent of a</span></span><br><span class="line"><span class="string">	 * phantom reference is always inaccessible, this method always returns</span></span><br><span class="line"><span class="string">	 * &lt;code&gt;null&lt;/code&gt;.</span></span><br><span class="line"><span class="string">	 *</span></span><br><span class="line"><span class="string">	 * @return  &lt;code&gt;null&lt;/code&gt;</span></span><br><span class="line"><span class="string">	 */</span></span><br><span class="line"><span class="string">	public T get() &#123;</span></span><br><span class="line"><span class="string">		return null;</span></span><br><span class="line"><span class="string">	&#125;</span></span><br><span class="line"><span class="string">	.....</span></span><br><span class="line"><span class="string">&#125;</span></span><br></pre></td></tr></table></figure></p>
<p>ReferenceQueue queue = new ReferenceQueue ();<br>PhantomReference pr = new PhantomReference (new Object(), queue);<br>pr.get();//返回null</p>
<h2 id="验证代码"><a href="#验证代码" class="headerlink" title="验证代码"></a>验证代码</h2><figure class="highlight bash"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br></pre></td><td class="code"><pre><span class="line">public class RefferenceDemo &#123;</span><br><span class="line">	static ReferenceQueue&lt;Object&gt; rq = new ReferenceQueue&lt;Object&gt;();</span><br><span class="line">	static Reference wr;</span><br><span class="line">	public static void <span class="function"><span class="title">test</span></span>() &#123;</span><br><span class="line">		wr = new WeakReference(new Object(),rq);</span><br><span class="line">		System.out.println(wr.get().hashCode());</span><br><span class="line">		</span><br><span class="line">	&#125;</span><br><span class="line">	public static void main(String[] args) &#123;</span><br><span class="line">		<span class="built_in">test</span>();</span><br><span class="line">		//Object o = wr.get(); //解除注释会增加强引用，则调用gc也不会回收，引用队列poll为null</span><br><span class="line">								//注释没有强引用，则调用gc会回收，引用队列poll为不为null</span><br><span class="line">		System.gc();</span><br><span class="line">		System.out.println(wr.get());</span><br><span class="line">		wr = rq.poll();</span><br><span class="line">		System.out.println(<span class="string">"poll:"</span>+wr+<span class="string">",getValue:"</span>+wr.get());</span><br><span class="line">		System.out.println(<span class="string">"poll:"</span>+rq.poll());</span><br><span class="line">		System.out.println(wr.get());</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>输出<br><figure class="highlight bash"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line">118352462</span><br><span class="line">null</span><br><span class="line">poll:java.lang.ref.WeakReference@5c647e05,getValue:null</span><br><span class="line">poll:null</span><br><span class="line">null</span><br></pre></td></tr></table></figure></p>
<h3 id="请移步"><a href="#请移步" class="headerlink" title="请移步"></a>请移步</h3><p>个人主页: <a href="http://yangyitao.top" target="_blank" rel="noopener">yangyitao.top</a></p>

      
    </div>
    
    <div class="article-info article-info-index">
      
      
      

      
      <div class="clearfix"></div>
    </div>
      
    
  </div>
  
</article>







  
    <article id="post-GC与垃圾回收分代" class="article article-type-post" itemscope itemprop="blogPost">
  
    <div class="article-meta">
      <a href="/blog/2019/03/30/GC与垃圾回收分代/" class="article-date">
  	<time datetime="2019-03-30T02:53:36.250Z" itemprop="datePublished">2019-03-30</time>
</a>
    </div>
  
  <div class="article-inner">
    
      <input type="hidden" class="isFancy" />
    
    
      <header class="article-header">
        
  
    <h1 itemprop="name">
      <a class="article-title" href="/blog/2019/03/30/GC与垃圾回收分代/">
        GC与垃圾回收分代
        
      </a>
    </h1>
  

      </header>
      
    
    <div class="article-entry" itemprop="articleBody">
      
        <p>欢迎查看Eetal的第十三篇博客–GC与垃圾回收分代</p>
<h2 id="gc与finalize"><a href="#gc与finalize" class="headerlink" title="gc与finalize"></a>gc与finalize</h2><p>网上很多博客简略的说确保对象死活需要经过两次标记这是错误的。<br>Object有个finalize，默认是空实现<br>被回收时会判断这个对象是否重写了finalize方法，如果没有就直接回收<br>否则会把该对象加入一个f队列（代表需要执行回收方法的队列）<br>jvm会分配一个执行finalize的线程去执行这个队列每个对象的finalize方法，如果在finalize方法中对象吧自己的this给不在finalize队列中的对象引用，则将其从finalize队列移除<br>jvm并不保证执行finalize的线程绝对会执行结束，而是超过一个固定时间以后就终止（防止死锁）。<br>finalize线程终止后，其中还保留的对象都会被回收</p>
<h2 id="判断对象是否存活"><a href="#判断对象是否存活" class="headerlink" title="判断对象是否存活"></a>判断对象是否存活</h2><p>以前采用过标记法，即每个对象加一个计数器，被引用了+1，取消引用-1.当为0代表可以回收<br>此种方法会导致无法处理循环引用(A引用B，B引用A且而GCroot没有任何对象引用A和B，则A和B永远不会被回收)，因此被遗弃了<br>现在普遍使用GCroot扫描方法</p>
<h2 id="GCRoot"><a href="#GCRoot" class="headerlink" title="GCRoot"></a>GCRoot</h2><p>以下对象可以作为GCroot<br>Class - 由系统类加载器(system class loader)加载的对象，这些类是不能够被回收的，他们可以以静态字段的方式保存持有其它对象。<br>        //其他类加载器加载的对象，jvm默认不回收，除非进行特殊指定<br>Thread - 活着的线程<br>Stack Local - Java方法栈的local变量或参数<br>JNI Local - JNI方法的local变量或参数<br>JNI Global - 全局JNI引用<br>Monitor Used - 用于同步的监控对象（锁）<br>Held by JVM - 用于JVM特殊目的由GC保留的对象，但实际上这个与JVM的实现是有关的。可能已知的一些类型是：系统类加载器、一些JVM知道的重要的异常类、一些用于处理异常的预分配对象以及一些自定义的类加载器等。</p>
<p>扫描过程:<br>    从GCroot开始扫描，如果可达的对象则为存活<br>    即为一个连通图的判断，不在图里的其他元素默认为死亡</p>
<h2 id="分代回收"><a href="#分代回收" class="headerlink" title="分代回收"></a>分代回收</h2><p>jdk1.7以前<br>java把堆内存分为两块，新生代和老生代<br>还有一块保存静态变量，常量和Class对象的永生代保存在方法区</p>
<p>新生代采用复制算法<br>老生代使用标记整理算法<br>永生代一般不回收，只有当需要加载Class而内存不够才会触发fullgc进行回收，会和老年代一起回收（标记整理）</p>
<p>新生代又分为 一块eden 和 两块survivor</p>
<p>参数:    指定新生代大小    -XX:NewSize<br>        指定老年代与新生代大小比例        -XX:NewRatio<br>        指定新生代中伊甸园和存活地大小比例: -XX:SurvivorRatio</p>
<p>刚开始new出来的对象都在伊甸园(eden)<br>然后一块survivor标记为存活地</p>
<h2 id="复制算法"><a href="#复制算法" class="headerlink" title="复制算法"></a>复制算法</h2><p>触发minor gc以后，会把另一块没有标记的空的survivor标记为存活地<br>会把eden中存活的对象和旧存活地的还活着的对象放进这块新的存活地,然后把旧存活地和伊甸园清空<br>当然如果存活地大小不足以容纳时，多余的对象会直接进入老年代<br>对象第一次进入survivor时，标记年龄为1<br>每次在survivor之间转移时年龄会增长，达到某个值时，就不进入新的存活地而是直接进入老年代<br>这个年龄可以通过jvm参数设置：-XX:MaxTenuringThreshold</p>
<h2 id="标记整理算法"><a href="#标记整理算法" class="headerlink" title="标记整理算法"></a>标记整理算法</h2><p>首先会遍历所有对象，标记还存活的对象，并清理掉死亡的对象，然后将存活的对象整理（挨到一起）<br>整理的目的和磁盘碎片压缩的道理一样，整理后才能留出更大的空间留给大对象，避免出现大量碎片<br>因为标记整理算法相对复制算法更慢，但是不需要额外的备用空间，<br>而minor gc触发频繁，老年代的gc触发较少，但是可能会累计较大空间<br>因此minor gc使用复制算法,major gc使用标记整理算法</p>
<p>对新生代触发的gc称为minor gc，而对老生代触发的gc称为major gc<br>fullgc是指触发所有的回收（包括对永久代的回收）</p>
<h2 id="垃圾回收器"><a href="#垃圾回收器" class="headerlink" title="垃圾回收器"></a>垃圾回收器</h2><h3 id="新生代"><a href="#新生代" class="headerlink" title="新生代"></a>新生代</h3><h4 id="Serial串行回收器"><a href="#Serial串行回收器" class="headerlink" title="Serial串行回收器"></a>Serial串行回收器</h4><p>基于单线程的回收器，在运行时会导致Stop The World，但是效率高，使用的算法就是复制算法<br>可以和CMS搭配使用</p>
<h4 id="ParNew回收器"><a href="#ParNew回收器" class="headerlink" title="ParNew回收器"></a>ParNew回收器</h4><p>Parallel New Generation<br>Serial回收器的多线程版本，因为是多线程版本，所以不用触发Stop the world<br>但是效率不太好，因为需要花开销在线程的切换调度销毁上<br>当然在多cpu电脑上会更有优势<br>可以和CMS搭配使用</p>
<h4 id="Parallel-Scavenge回收器"><a href="#Parallel-Scavenge回收器" class="headerlink" title="Parallel Scavenge回收器"></a>Parallel Scavenge回收器</h4><p>与ParNew类似，都是复制算法的并行收集器<br>但是Parallel Scavenge的目标是达到一个可控的吞吐量<br>吞吐量=程序运行时间/（程序运行时间+GC时间）<br>Parallel Scavenge提供了两个参数用以精确控制吞吐量<br>分别是用以控制最大GC停顿时间的-XX:MaxGCPauseMillis及直接控制吞吐量的参数-XX:GCTimeRatio.<br>同时可以设置垃圾自适应调配策略，由虚拟机自动调优<br>由于是Parallel Scavenge没有使用原本HotSpot其它GC通用的那个GC框架，所以不能跟使用了那个框架的CMS搭配使用。</p>
<h3 id="老年代"><a href="#老年代" class="headerlink" title="老年代"></a>老年代</h3><h4 id="SerialOld回收器"><a href="#SerialOld回收器" class="headerlink" title="SerialOld回收器"></a>SerialOld回收器</h4><p>Serial的老年代版本，还是单线程也会触发Stop the world，不过使用的是标记整理算法</p>
<h4 id="ParallelOld回收器"><a href="#ParallelOld回收器" class="headerlink" title="ParallelOld回收器"></a>ParallelOld回收器</h4><p>Parallel Scavenge的年老代版,使用标记整理算法，并行</p>
<h4 id="CMS回收器"><a href="#CMS回收器" class="headerlink" title="CMS回收器"></a>CMS回收器</h4><p>Concurrent Mark Sweep，并发回收器，旨在减少STW时间（通过两次标记，第二次只查看dirty的）<br>在G1出现前的主流一般server版本jvm就是ParNew+CMS<br>过程<br>初始标记：该阶段只标记GC Root节点直接引用的老年代节点，会造成STW，但是时间很短。（因为只标记被直接引用的）<br>并发标记：GC ROOT TRACING。遍历老年代，然后标记所有存活的对象（包括不是gcRoot直接引用的），它会根据上个阶段找到的 GC Roots 遍历查找<br>          在并发标记阶段被修改的节点（新降临到老年代的对象以及在并发阶段被修改了的对象）的对象会被标记为dirty，加入Dirty队列<br>重新标记：stop the world<br>          遍历DirtyCard，更新标记被修改的老年代对象<br>          停顿时间比初始标记稍长，但远比并发标记短<br>并发清理：遍历老年代清理死亡对象，整理空间</p>
<h3 id="请移步"><a href="#请移步" class="headerlink" title="请移步"></a>请移步</h3><p>个人主页: <a href="http://yangyitao.top" target="_blank" rel="noopener">yangyitao.top</a></p>

      
    </div>
    
    <div class="article-info article-info-index">
      
      
      

      
      <div class="clearfix"></div>
    </div>
      
    
  </div>
  
</article>







  
    <article id="post-并发基石-AQS与Condition" class="article article-type-post" itemscope itemprop="blogPost">
  
    <div class="article-meta">
      <a href="/blog/2019/03/26/并发基石-AQS与Condition/" class="article-date">
  	<time datetime="2019-03-26T00:28:37.930Z" itemprop="datePublished">2019-03-26</time>
</a>
    </div>
  
  <div class="article-inner">
    
      <input type="hidden" class="isFancy" />
    
    
      <header class="article-header">
        
  
    <h1 itemprop="name">
      <a class="article-title" href="/blog/2019/03/26/并发基石-AQS与Condition/">
        并发基石-AQS与Condition
        
      </a>
    </h1>
  

      </header>
      
    
    <div class="article-entry" itemprop="articleBody">
      
        <p>欢迎查看Eetal的第十二篇博客–并发基石-AQS与Condition</p>
<h2 id="Condition"><a href="#Condition" class="headerlink" title="Condition"></a>Condition</h2><p>在前面的博客JUC相关中，已经初略介绍了Condition接口，代表一个条件，可以阻塞、唤醒一个条件队列<br>今天来具体讲讲其与AQS（AbstractQueueSynchronizer）的实现源码<br>Condition中的加入条件队列，阻塞，唤醒等等操作都是由AbstractQueueSynchronizer或其子类方法完成</p>
<h2 id="AQS"><a href="#AQS" class="headerlink" title="AQS"></a>AQS</h2><p>AbstractQueueSynchronizer是java提供的队列同步器，个人理解更贴近一个线程调度的管理者<br>首先我们了解其内部类Node，Node既可以代表Condition的一个条件队列（单向链表），也可以代表当前锁资源的同步队列（双向链表）中的一个竞争线程的节点<br>先看其结构</p>
<h3 id="Node"><a href="#Node" class="headerlink" title="Node"></a>Node</h3><figure class="highlight bash"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br></pre></td><td class="code"><pre><span class="line">static final class Node &#123;</span><br><span class="line">        /** Marker to indicate a node is waiting <span class="keyword">in</span> shared mode */</span><br><span class="line">        static final Node SHARED = new Node();</span><br><span class="line">        /** Marker to indicate a node is waiting <span class="keyword">in</span> exclusive mode */</span><br><span class="line">        static final Node EXCLUSIVE = null;</span><br><span class="line"></span><br><span class="line">        /** waitStatus value to indicate thread has cancelled */</span><br><span class="line">        static final int CANCELLED =  1;</span><br><span class="line">        /** waitStatus value to indicate successor<span class="string">'s thread needs unparking */</span></span><br><span class="line"><span class="string">        static final int SIGNAL    = -1;</span></span><br><span class="line"><span class="string">        /** waitStatus value to indicate thread is waiting on condition */</span></span><br><span class="line"><span class="string">        static final int CONDITION = -2;</span></span><br><span class="line"><span class="string">        /**</span></span><br><span class="line"><span class="string">         * waitStatus value to indicate the next acquireShared should</span></span><br><span class="line"><span class="string">         * unconditionally propagate</span></span><br><span class="line"><span class="string">         */</span></span><br><span class="line"><span class="string">        static final int PROPAGATE = -3;</span></span><br><span class="line"><span class="string"></span></span><br><span class="line"><span class="string">        /**</span></span><br><span class="line"><span class="string">         * Status field, taking on only the values:</span></span><br><span class="line"><span class="string">         *   SIGNAL:     The successor of this node is (or will soon be)</span></span><br><span class="line"><span class="string">         *               blocked (via park), so the current node must</span></span><br><span class="line"><span class="string">         *               unpark its successor when it releases or</span></span><br><span class="line"><span class="string">         *               cancels. To avoid races, acquire methods must</span></span><br><span class="line"><span class="string">         *               first indicate they need a signal,</span></span><br><span class="line"><span class="string">         *               then retry the atomic acquire, and then,</span></span><br><span class="line"><span class="string">         *               on failure, block.</span></span><br><span class="line"><span class="string">         *   CANCELLED:  This node is cancelled due to timeout or interrupt.</span></span><br><span class="line"><span class="string">         *               Nodes never leave this state. In particular,</span></span><br><span class="line"><span class="string">         *               a thread with cancelled node never again blocks.</span></span><br><span class="line"><span class="string">         *   CONDITION:  This node is currently on a condition queue.</span></span><br><span class="line"><span class="string">         *               It will not be used as a sync queue node</span></span><br><span class="line"><span class="string">         *               until transferred, at which time the status</span></span><br><span class="line"><span class="string">         *               will be set to 0. (Use of this value here has</span></span><br><span class="line"><span class="string">         *               nothing to do with the other uses of the</span></span><br><span class="line"><span class="string">         *               field, but simplifies mechanics.)</span></span><br><span class="line"><span class="string">         *   PROPAGATE:  A releaseShared should be propagated to other</span></span><br><span class="line"><span class="string">         *               nodes. This is set (for head node only) in</span></span><br><span class="line"><span class="string">         *               doReleaseShared to ensure propagation</span></span><br><span class="line"><span class="string">         *               continues, even if other operations have</span></span><br><span class="line"><span class="string">         *               since intervened.</span></span><br><span class="line"><span class="string">         *   0:          None of the above</span></span><br><span class="line"><span class="string">         *</span></span><br><span class="line"><span class="string">         * The values are arranged numerically to simplify use.</span></span><br><span class="line"><span class="string">         * Non-negative values mean that a node doesn'</span>t need to</span><br><span class="line">         * signal. So, most code doesn<span class="string">'t need to check for particular</span></span><br><span class="line"><span class="string">         * values, just for sign.</span></span><br><span class="line"><span class="string">         *</span></span><br><span class="line"><span class="string">         * The field is initialized to 0 for normal sync nodes, and</span></span><br><span class="line"><span class="string">         * CONDITION for condition nodes.  It is modified using CAS</span></span><br><span class="line"><span class="string">         * (or when possible, unconditional volatile writes).</span></span><br><span class="line"><span class="string">         */</span></span><br><span class="line"><span class="string">        volatile int waitStatus;</span></span><br><span class="line"><span class="string"></span></span><br><span class="line"><span class="string">        /**</span></span><br><span class="line"><span class="string">         * Link to predecessor node that current node/thread relies on</span></span><br><span class="line"><span class="string">         * for checking waitStatus. Assigned during enqueuing, and nulled</span></span><br><span class="line"><span class="string">         * out (for sake of GC) only upon dequeuing.  Also, upon</span></span><br><span class="line"><span class="string">         * cancellation of a predecessor, we short-circuit while</span></span><br><span class="line"><span class="string">         * finding a non-cancelled one, which will always exist</span></span><br><span class="line"><span class="string">         * because the head node is never cancelled: A node becomes</span></span><br><span class="line"><span class="string">         * head only as a result of successful acquire. A</span></span><br><span class="line"><span class="string">         * cancelled thread never succeeds in acquiring, and a thread only</span></span><br><span class="line"><span class="string">         * cancels itself, not any other node.</span></span><br><span class="line"><span class="string">         */</span></span><br><span class="line"><span class="string">        volatile Node prev;</span></span><br><span class="line"><span class="string"></span></span><br><span class="line"><span class="string">        /**</span></span><br><span class="line"><span class="string">         * Link to the successor node that the current node/thread</span></span><br><span class="line"><span class="string">         * unparks upon release. Assigned during enqueuing, adjusted</span></span><br><span class="line"><span class="string">         * when bypassing cancelled predecessors, and nulled out (for</span></span><br><span class="line"><span class="string">         * sake of GC) when dequeued.  The enq operation does not</span></span><br><span class="line"><span class="string">         * assign next field of a predecessor until after attachment,</span></span><br><span class="line"><span class="string">         * so seeing a null next field does not necessarily mean that</span></span><br><span class="line"><span class="string">         * node is at end of queue. However, if a next field appears</span></span><br><span class="line"><span class="string">         * to be null, we can scan prev'</span>s from the tail to</span><br><span class="line">         * double-check.  The next field of cancelled nodes is <span class="built_in">set</span> to</span><br><span class="line">         * point to the node itself instead of null, to make life</span><br><span class="line">         * easier <span class="keyword">for</span> isOnSyncQueue.</span><br><span class="line">         */</span><br><span class="line">        volatile Node next;</span><br><span class="line"></span><br><span class="line">        /**</span><br><span class="line">         * The thread that enqueued this node.  Initialized on</span><br><span class="line">         * construction and nulled out after use.</span><br><span class="line">         */</span><br><span class="line">        volatile Thread thread;</span><br><span class="line"></span><br><span class="line">        /**</span><br><span class="line">         * Link to next node waiting on condition, or the special</span><br><span class="line">         * value SHARED.  Because condition queues are accessed only</span><br><span class="line">         * when holding <span class="keyword">in</span> exclusive mode, we just need a simple</span><br><span class="line">         * linked queue to hold nodes <span class="keyword">while</span> they are waiting on</span><br><span class="line">         * conditions. They are <span class="keyword">then</span> transferred to the queue to</span><br><span class="line">         * re-acquire. And because conditions can only be exclusive,</span><br><span class="line">         * we save a field by using special value to indicate shared</span><br><span class="line">         * mode.</span><br><span class="line">         */</span><br><span class="line">        Node nextWaiter;</span><br><span class="line"></span><br><span class="line">        /**</span><br><span class="line">         * Returns <span class="literal">true</span> <span class="keyword">if</span> node is waiting <span class="keyword">in</span> shared mode.</span><br><span class="line">         */</span><br><span class="line">        final boolean <span class="function"><span class="title">isShared</span></span>() &#123;</span><br><span class="line">            <span class="built_in">return</span> nextWaiter == SHARED;</span><br><span class="line">        &#125;</span><br><span class="line">		...</span><br><span class="line">	&#125;</span><br></pre></td></tr></table></figure>
<p>Node中保存有竞争锁的线程对象<br>prev属性代表同步队列中的上一个节点<br>next属性代表同步队列中的下一个节点<br>nextWaiter属性，如果Node处于条件队列中，则nextWaiter指向条件队列中的下一个Node<br>nextWaiter属性，如果Node处于同步队列中，则nextWaiter代表同步模式，SHARE和EXCLUSIVE<br>因为条件队列中的都是互斥，所以不需要保存该mode</p>
<h3 id="执行开始"><a href="#执行开始" class="headerlink" title="执行开始"></a>执行开始</h3><p>首先Condition调用了await方法<br><figure class="highlight bash"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br><span class="line">109</span><br><span class="line">110</span><br><span class="line">111</span><br><span class="line">112</span><br><span class="line">113</span><br><span class="line">114</span><br><span class="line">115</span><br></pre></td><td class="code"><pre><span class="line">final int fullyRelease(Node node) &#123;</span><br><span class="line">	boolean failed = <span class="literal">true</span>;</span><br><span class="line">	try &#123;</span><br><span class="line">		int savedState = getState();</span><br><span class="line">		<span class="keyword">if</span> (release(savedState)) &#123;</span><br><span class="line">			failed = <span class="literal">false</span>;</span><br><span class="line">			<span class="built_in">return</span> savedState;</span><br><span class="line">		&#125; <span class="keyword">else</span> &#123;</span><br><span class="line">			throw new IllegalMonitorStateException();</span><br><span class="line">		&#125;</span><br><span class="line">	&#125; finally &#123;</span><br><span class="line">		<span class="keyword">if</span> (failed)</span><br><span class="line">			node.waitStatus = Node.CANCELLED;</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br><span class="line"> public final void await() throws InterruptedException &#123;</span><br><span class="line">            <span class="keyword">if</span> (Thread.interrupted())</span><br><span class="line">                throw new InterruptedException();</span><br><span class="line">            Node node = addConditionWaiter();</span><br><span class="line">            int savedState = fullyRelease(node);</span><br><span class="line">            int interruptMode = 0;</span><br><span class="line">            <span class="keyword">while</span> (!isOnSyncQueue(node)) &#123;</span><br><span class="line">                LockSupport.park(this);</span><br><span class="line">                <span class="keyword">if</span> ((interruptMode = checkInterruptWhileWaiting(node)) != 0)</span><br><span class="line">                    <span class="built_in">break</span>;</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">if</span> (acquireQueued(node, savedState) &amp;&amp; interruptMode != THROW_IE)</span><br><span class="line">                interruptMode = REINTERRUPT;</span><br><span class="line">            <span class="keyword">if</span> (node.nextWaiter != null) // clean up <span class="keyword">if</span> cancelled</span><br><span class="line">                unlinkCancelledWaiters();</span><br><span class="line">            <span class="keyword">if</span> (interruptMode != 0)</span><br><span class="line">                reportInterruptAfterWait(interruptMode);</span><br><span class="line">        &#125;</span><br><span class="line">final boolean acquireQueued(final Node node, int arg) &#123;</span><br><span class="line">        boolean failed = <span class="literal">true</span>;</span><br><span class="line">        try &#123;</span><br><span class="line">            boolean interrupted = <span class="literal">false</span>;</span><br><span class="line">            <span class="keyword">for</span> (;;) &#123;</span><br><span class="line">                final Node p = node.predecessor();</span><br><span class="line">                <span class="keyword">if</span> (p == head &amp;&amp; tryAcquire(arg)) &#123;</span><br><span class="line">                    setHead(node);</span><br><span class="line">                    p.next = null; // <span class="built_in">help</span> GC</span><br><span class="line">                    failed = <span class="literal">false</span>;</span><br><span class="line">                    <span class="built_in">return</span> interrupted;</span><br><span class="line">                &#125;</span><br><span class="line">                <span class="keyword">if</span> (shouldParkAfterFailedAcquire(p, node) &amp;&amp;</span><br><span class="line">                    parkAndCheckInterrupt())</span><br><span class="line">                    interrupted = <span class="literal">true</span>;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125; finally &#123;</span><br><span class="line">            <span class="keyword">if</span> (failed)</span><br><span class="line">                cancelAcquire(node);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">	 private static boolean shouldParkAfterFailedAcquire(Node pred, Node node) &#123;</span><br><span class="line">        int ws = pred.waitStatus;</span><br><span class="line">        <span class="keyword">if</span> (ws == Node.SIGNAL)</span><br><span class="line">            /*</span><br><span class="line">             * This node has already <span class="built_in">set</span> status asking a release</span><br><span class="line">             * to signal it, so it can safely park.</span><br><span class="line">             */</span><br><span class="line">            <span class="built_in">return</span> <span class="literal">true</span>;</span><br><span class="line">        <span class="keyword">if</span> (ws &gt; 0) &#123;</span><br><span class="line">            /*</span><br><span class="line">             * Predecessor was cancelled. Skip over predecessors and</span><br><span class="line">             * indicate retry.</span><br><span class="line">             */</span><br><span class="line">            <span class="keyword">do</span> &#123;</span><br><span class="line">                node.prev = pred = pred.prev;</span><br><span class="line">            &#125; <span class="keyword">while</span> (pred.waitStatus &gt; 0);</span><br><span class="line">            pred.next = node;</span><br><span class="line">        &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">            /*</span><br><span class="line">             * waitStatus must be 0 or PROPAGATE.  Indicate that we</span><br><span class="line">             * need a signal, but don<span class="string">'t park yet.  Caller will need to</span></span><br><span class="line"><span class="string">             * retry to make sure it cannot acquire before parking.</span></span><br><span class="line"><span class="string">             */</span></span><br><span class="line"><span class="string">            compareAndSetWaitStatus(pred, ws, Node.SIGNAL);</span></span><br><span class="line"><span class="string">        &#125;</span></span><br><span class="line"><span class="string">        return false;</span></span><br><span class="line"><span class="string">    &#125;</span></span><br><span class="line"><span class="string">	private Node addConditionWaiter() &#123;</span></span><br><span class="line"><span class="string">	Node t = lastWaiter;</span></span><br><span class="line"><span class="string">	// If lastWaiter is cancelled, clean out.</span></span><br><span class="line"><span class="string">	if (t != null &amp;&amp; t.waitStatus != Node.CONDITION) &#123;</span></span><br><span class="line"><span class="string">		unlinkCancelledWaiters();</span></span><br><span class="line"><span class="string">		t = lastWaiter;</span></span><br><span class="line"><span class="string">	&#125;</span></span><br><span class="line"><span class="string">	Node node = new Node(Thread.currentThread(), Node.CONDITION);</span></span><br><span class="line"><span class="string">	if (t == null)</span></span><br><span class="line"><span class="string">		firstWaiter = node;</span></span><br><span class="line"><span class="string">	else</span></span><br><span class="line"><span class="string">		t.nextWaiter = node;</span></span><br><span class="line"><span class="string">	lastWaiter = node;</span></span><br><span class="line"><span class="string">	return node;</span></span><br><span class="line"><span class="string">	&#125;</span></span><br><span class="line"><span class="string">	private void unlinkCancelledWaiters() &#123;</span></span><br><span class="line"><span class="string">	Node t = firstWaiter;</span></span><br><span class="line"><span class="string">	Node trail = null;</span></span><br><span class="line"><span class="string">	while (t != null) &#123;</span></span><br><span class="line"><span class="string">		Node next = t.nextWaiter;</span></span><br><span class="line"><span class="string">		if (t.waitStatus != Node.CONDITION) &#123;</span></span><br><span class="line"><span class="string">			t.nextWaiter = null;</span></span><br><span class="line"><span class="string">			if (trail == null)</span></span><br><span class="line"><span class="string">				firstWaiter = next;</span></span><br><span class="line"><span class="string">			else</span></span><br><span class="line"><span class="string">				trail.nextWaiter = next;</span></span><br><span class="line"><span class="string">			if (next == null)</span></span><br><span class="line"><span class="string">				lastWaiter = trail;</span></span><br><span class="line"><span class="string">		&#125;</span></span><br><span class="line"><span class="string">		else</span></span><br><span class="line"><span class="string">			trail = t;</span></span><br><span class="line"><span class="string">		t = next;</span></span><br><span class="line"><span class="string">	&#125;</span></span><br><span class="line"><span class="string">&#125;</span></span><br></pre></td></tr></table></figure></p>
<p>简单捋一下await的逻辑，首先创建一个Node到等待队列里，然后释放资源<br>接着不断循环判断是否已经在同步队列里了，不在则挂起线程直到被UnPark<br>当处于同步队列里且被唤醒后就会调用请求资源的方法<br>不断的自旋尝试获取锁，如果处于头节点则获取得到资源，恢复执行后续代码<br>如果他不是同步队列的头节点，则判断他在同步队列里的前驱节点<br>如果前驱节点也处于请求释放的状态，因为总是唤醒前面的节点，所以这个节点这时候就可以安全的挂起<br>如果前驱节点处于取消状态，则不断清理被前驱取消的节点，直到第一个处于非取消状态的节点，将该节点作为当前结点的前驱<br>剩下的waitstatus中-2代表在条件队列已经不需要考虑，只剩下0（初始状态需要请求）和-3（读写锁的读锁请求到共享资源时，标记为该状态代表可以执行）<br>就把前驱节点更改为请求释放signal的状态<br>最后把所有已经不是条件等待状态的node移出队列</p>
<p>如果调用了signal方法<br><figure class="highlight bash"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br><span class="line">109</span><br><span class="line">110</span><br><span class="line">111</span><br><span class="line">112</span><br><span class="line">113</span><br><span class="line">114</span><br><span class="line">115</span><br><span class="line">116</span><br><span class="line">117</span><br></pre></td><td class="code"><pre><span class="line">public final void <span class="function"><span class="title">signal</span></span>() &#123;</span><br><span class="line">            <span class="keyword">if</span> (!isHeldExclusively())</span><br><span class="line">                throw new IllegalMonitorStateException();</span><br><span class="line">            Node first = firstWaiter;</span><br><span class="line">            <span class="keyword">if</span> (first != null)</span><br><span class="line">                doSignal(first);</span><br><span class="line">        &#125;</span><br><span class="line">private void doSignal(Node first) &#123;</span><br><span class="line">	<span class="keyword">do</span> &#123;</span><br><span class="line">		<span class="keyword">if</span> ( (firstWaiter = first.nextWaiter) == null)</span><br><span class="line">			lastWaiter = null;</span><br><span class="line">		first.nextWaiter = null;</span><br><span class="line">	&#125; <span class="keyword">while</span> (!transferForSignal(first) &amp;&amp;</span><br><span class="line">			 (first = firstWaiter) != null);</span><br><span class="line">&#125;    </span><br><span class="line">final boolean transferForSignal(Node node) &#123;</span><br><span class="line">        /*</span><br><span class="line">         * If cannot change waitStatus, the node has been cancelled.</span><br><span class="line">         */</span><br><span class="line">        <span class="keyword">if</span> (!compareAndSetWaitStatus(node, Node.CONDITION, 0))</span><br><span class="line">            <span class="built_in">return</span> <span class="literal">false</span>;</span><br><span class="line"></span><br><span class="line">        /*</span><br><span class="line">         * Splice onto queue and try to <span class="built_in">set</span> waitStatus of predecessor to</span><br><span class="line">         * indicate that thread is (probably) waiting. If cancelled or</span><br><span class="line">         * attempt to <span class="built_in">set</span> waitStatus fails, wake up to resync (<span class="keyword">in</span> <span class="built_in">which</span></span><br><span class="line">         * <span class="keyword">case</span> the waitStatus can be transiently and harmlessly wrong).</span><br><span class="line">         */</span><br><span class="line">        Node p = enq(node);</span><br><span class="line">        int ws = p.waitStatus;</span><br><span class="line">        <span class="keyword">if</span> (ws &gt; 0 || !compareAndSetWaitStatus(p, ws, Node.SIGNAL))</span><br><span class="line">            LockSupport.unpark(node.thread);</span><br><span class="line">        <span class="built_in">return</span> <span class="literal">true</span>;</span><br><span class="line">    &#125;</span><br><span class="line">private Node enq(final Node node) &#123;</span><br><span class="line">        <span class="keyword">for</span> (;;) &#123;</span><br><span class="line">            Node t = tail;</span><br><span class="line">            <span class="keyword">if</span> (t == null) &#123; // Must initialize</span><br><span class="line">                <span class="keyword">if</span> (compareAndSetHead(new Node()))</span><br><span class="line">                    tail = head;</span><br><span class="line">            &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">                node.prev = t;</span><br><span class="line">                <span class="keyword">if</span> (compareAndSetTail(t, node)) &#123;</span><br><span class="line">                    t.next = node;</span><br><span class="line">                    <span class="built_in">return</span> t;</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line"> public final void await() throws InterruptedException &#123;</span><br><span class="line">            <span class="keyword">if</span> (Thread.interrupted())</span><br><span class="line">                throw new InterruptedException();</span><br><span class="line">            Node node = addConditionWaiter();</span><br><span class="line">            int savedState = fullyRelease(node);</span><br><span class="line">            int interruptMode = 0;</span><br><span class="line">            <span class="keyword">while</span> (!isOnSyncQueue(node)) &#123;</span><br><span class="line">                LockSupport.park(this);</span><br><span class="line">                <span class="keyword">if</span> ((interruptMode = checkInterruptWhileWaiting(node)) != 0)</span><br><span class="line">                    <span class="built_in">break</span>;</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">if</span> (acquireQueued(node, savedState) &amp;&amp; interruptMode != THROW_IE)</span><br><span class="line">                interruptMode = REINTERRUPT;</span><br><span class="line">            <span class="keyword">if</span> (node.nextWaiter != null) // clean up <span class="keyword">if</span> cancelled</span><br><span class="line">                unlinkCancelledWaiters();</span><br><span class="line">            <span class="keyword">if</span> (interruptMode != 0)</span><br><span class="line">                reportInterruptAfterWait(interruptMode);</span><br><span class="line">        &#125;</span><br><span class="line">final int fullyRelease(Node node) &#123;</span><br><span class="line">	boolean failed = <span class="literal">true</span>;</span><br><span class="line">	try &#123;</span><br><span class="line">		int savedState = getState();</span><br><span class="line">		<span class="keyword">if</span> (release(savedState)) &#123;</span><br><span class="line">			failed = <span class="literal">false</span>;</span><br><span class="line">			<span class="built_in">return</span> savedState;</span><br><span class="line">		&#125; <span class="keyword">else</span> &#123;</span><br><span class="line">			throw new IllegalMonitorStateException();</span><br><span class="line">		&#125;</span><br><span class="line">	&#125; finally &#123;</span><br><span class="line">		<span class="keyword">if</span> (failed)</span><br><span class="line">			node.waitStatus = Node.CANCELLED;</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br><span class="line">public final boolean release(int arg) &#123;</span><br><span class="line">        <span class="keyword">if</span> (tryRelease(arg)) &#123;</span><br><span class="line">            Node h = head;</span><br><span class="line">            <span class="keyword">if</span> (h != null &amp;&amp; h.waitStatus != 0)</span><br><span class="line">                unparkSuccessor(h);</span><br><span class="line">            <span class="built_in">return</span> <span class="literal">true</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="built_in">return</span> <span class="literal">false</span>;</span><br><span class="line">    &#125;</span><br><span class="line">private void unparkSuccessor(Node node) &#123;</span><br><span class="line">	/*</span><br><span class="line">	 * If status is negative (i.e., possibly needing signal) try</span><br><span class="line">	 * to clear <span class="keyword">in</span> anticipation of signalling.  It is OK <span class="keyword">if</span> this</span><br><span class="line">	 * fails or <span class="keyword">if</span> status is changed by waiting thread.</span><br><span class="line">	 */</span><br><span class="line">	int ws = node.waitStatus;</span><br><span class="line">	<span class="keyword">if</span> (ws &lt; 0)</span><br><span class="line">		compareAndSetWaitStatus(node, ws, 0);</span><br><span class="line"></span><br><span class="line">	/*</span><br><span class="line">	 * Thread to unpark is held <span class="keyword">in</span> successor, <span class="built_in">which</span> is normally</span><br><span class="line">	 * just the next node.  But <span class="keyword">if</span> cancelled or apparently null,</span><br><span class="line">	 * traverse backwards from tail to find the actual</span><br><span class="line">	 * non-cancelled successor.</span><br><span class="line">	 */</span><br><span class="line">	Node s = node.next;</span><br><span class="line">	<span class="keyword">if</span> (s == null || s.waitStatus &gt; 0) &#123;</span><br><span class="line">		s = null;</span><br><span class="line">		<span class="keyword">for</span> (Node t = tail; t != null &amp;&amp; t != node; t = t.prev)</span><br><span class="line">			<span class="keyword">if</span> (t.waitStatus &lt;= 0)</span><br><span class="line">				s = t;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">if</span> (s != null)</span><br><span class="line">		LockSupport.unpark(s.thread);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<p>默认唤醒条件队列从头节点开始往后找到的第一个处于非取消状态的节点<br>把其加入同步队列，并更改状态<br>如果更改失败说明这其间该节点被取消了，则返回失败继续往后寻找节点唤醒<br>如果更改成功，则判断同步队列的前驱节点的状态，如果该节点被取消了则唤醒当前新加入的线程53<br>原因是进入同步队列时，只有作为头节点才会立即请求资源<br>否则，同步队列里只有释放资源时才会再次Unpark同步队列下一个线程<br>因此防止前面的节点未获取到资源就取消导致后续没有调起下一个Unpark<br>最好最安全的方法是如果前驱节点突然取消了，unPark一下<br>这样即使还有别的线程在占用资源，他也会在获取资源失败后再次进入park</p>
<h3 id="AQS中的实现"><a href="#AQS中的实现" class="headerlink" title="AQS中的实现"></a>AQS中的实现</h3><p>添加节点，默认添加到尾部<br><figure class="highlight bash"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br></pre></td><td class="code"><pre><span class="line">private Node addWaiter(Node mode) &#123;</span><br><span class="line">        Node node = new Node(Thread.currentThread(), mode);</span><br><span class="line">        // Try the fast path of enq; backup to full enq on failure</span><br><span class="line">        Node pred = tail;</span><br><span class="line">        <span class="keyword">if</span> (pred != null) &#123;</span><br><span class="line">            node.prev = pred;</span><br><span class="line">            <span class="keyword">if</span> (compareAndSetTail(pred, node)) &#123;</span><br><span class="line">                pred.next = node;</span><br><span class="line">                <span class="built_in">return</span> node;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        enq(node);</span><br><span class="line">        <span class="built_in">return</span> node;</span><br><span class="line">    &#125;</span><br></pre></td></tr></table></figure></p>
<p>条件队列的移除上面已经分析了，那同步队列的呢?</p>
<p>现在我们回到一开始await被signal唤醒后自旋请求资源的地方来看请求资源的方法</p>
<figure class="highlight bash"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br></pre></td><td class="code"><pre><span class="line">final boolean acquireQueued(final Node node, int arg) &#123;</span><br><span class="line">        boolean failed = <span class="literal">true</span>;</span><br><span class="line">        try &#123;</span><br><span class="line">            boolean interrupted = <span class="literal">false</span>;</span><br><span class="line">            <span class="keyword">for</span> (;;) &#123;</span><br><span class="line">                final Node p = node.predecessor();</span><br><span class="line">                <span class="keyword">if</span> (p == head &amp;&amp; tryAcquire(arg)) &#123;</span><br><span class="line">                    setHead(node);</span><br><span class="line">                    p.next = null; // <span class="built_in">help</span> GC</span><br><span class="line">                    failed = <span class="literal">false</span>;</span><br><span class="line">                    <span class="built_in">return</span> interrupted;</span><br><span class="line">                &#125;</span><br><span class="line">                <span class="keyword">if</span> (shouldParkAfterFailedAcquire(p, node) &amp;&amp;</span><br><span class="line">                    parkAndCheckInterrupt())</span><br><span class="line">                    interrupted = <span class="literal">true</span>;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125; finally &#123;</span><br><span class="line">            <span class="keyword">if</span> (failed)</span><br><span class="line">                cancelAcquire(node);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">private void cancelAcquire(Node node) &#123;</span><br><span class="line">        // Ignore <span class="keyword">if</span> node doesn<span class="string">'t exist</span></span><br><span class="line"><span class="string">        if (node == null)</span></span><br><span class="line"><span class="string">            return;</span></span><br><span class="line"><span class="string"></span></span><br><span class="line"><span class="string">        node.thread = null;</span></span><br><span class="line"><span class="string"></span></span><br><span class="line"><span class="string">        // Skip cancelled predecessors</span></span><br><span class="line"><span class="string">        Node pred = node.prev;</span></span><br><span class="line"><span class="string">        while (pred.waitStatus &gt; 0)</span></span><br><span class="line"><span class="string">            node.prev = pred = pred.prev;</span></span><br><span class="line"><span class="string"></span></span><br><span class="line"><span class="string">        // predNext is the apparent node to unsplice. CASes below will</span></span><br><span class="line"><span class="string">        // fail if not, in which case, we lost race vs another cancel</span></span><br><span class="line"><span class="string">        // or signal, so no further action is necessary.</span></span><br><span class="line"><span class="string">        Node predNext = pred.next;</span></span><br><span class="line"><span class="string"></span></span><br><span class="line"><span class="string">        // Can use unconditional write instead of CAS here.</span></span><br><span class="line"><span class="string">        // After this atomic step, other Nodes can skip past us.</span></span><br><span class="line"><span class="string">        // Before, we are free of interference from other threads.</span></span><br><span class="line"><span class="string">        node.waitStatus = Node.CANCELLED;</span></span><br><span class="line"><span class="string"></span></span><br><span class="line"><span class="string">        // If we are the tail, remove ourselves.</span></span><br><span class="line"><span class="string">        if (node == tail &amp;&amp; compareAndSetTail(node, pred)) &#123;</span></span><br><span class="line"><span class="string">            compareAndSetNext(pred, predNext, null);</span></span><br><span class="line"><span class="string">        &#125; else &#123;</span></span><br><span class="line"><span class="string">            // If successor needs signal, try to set pred'</span>s next-link</span><br><span class="line">            // so it will get one. Otherwise wake it up to propagate.</span><br><span class="line">            int ws;</span><br><span class="line">            <span class="keyword">if</span> (pred != head &amp;&amp;</span><br><span class="line">                ((ws = pred.waitStatus) == Node.SIGNAL ||</span><br><span class="line">                 (ws &lt;= 0 &amp;&amp; compareAndSetWaitStatus(pred, ws, Node.SIGNAL))) &amp;&amp;</span><br><span class="line">                pred.thread != null) &#123;</span><br><span class="line">                Node next = node.next;</span><br><span class="line">                <span class="keyword">if</span> (next != null &amp;&amp; next.waitStatus &lt;= 0)</span><br><span class="line">                    compareAndSetNext(pred, predNext, next);</span><br><span class="line">            &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">                unparkSuccessor(node);</span><br><span class="line">            &#125;</span><br><span class="line"></span><br><span class="line">            node.next = node; // <span class="built_in">help</span> GC</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">	 final Node predecessor() throws NullPointerException &#123;</span><br><span class="line">            Node p = prev;</span><br><span class="line">            <span class="keyword">if</span> (p == null)</span><br><span class="line">                throw new NullPointerException();</span><br><span class="line">            <span class="keyword">else</span></span><br><span class="line">                <span class="built_in">return</span> p;</span><br><span class="line">        &#125;</span><br><span class="line">	//---默认Sync使用不公平，此处作为示例	</span><br><span class="line">	final boolean nonfairTryAcquire(int acquires) &#123;</span><br><span class="line">            final Thread current = Thread.currentThread();</span><br><span class="line">            int c = getState();</span><br><span class="line">            <span class="keyword">if</span> (c == 0) &#123;</span><br><span class="line">                <span class="keyword">if</span> (compareAndSetState(0, acquires)) &#123;</span><br><span class="line">                    setExclusiveOwnerThread(current);</span><br><span class="line">                    <span class="built_in">return</span> <span class="literal">true</span>;</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">else</span> <span class="keyword">if</span> (current == getExclusiveOwnerThread()) &#123;</span><br><span class="line">                int nextc = c + acquires;</span><br><span class="line">                <span class="keyword">if</span> (nextc &lt; 0) // overflow</span><br><span class="line">                    throw new Error(<span class="string">"Maximum lock count exceeded"</span>);</span><br><span class="line">                setState(nextc);</span><br><span class="line">                <span class="built_in">return</span> <span class="literal">true</span>;</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="built_in">return</span> <span class="literal">false</span>;</span><br><span class="line">        &#125;</span><br></pre></td></tr></table></figure>
<p>当请求资源时什么情况执行finally<br>1.前驱节点为null，空指针异常failed变量为初始值true，此时取消资源会把自己移除出同步队列（因为头指针是特殊标记，不代表实际请求资源的Node）<br>    —在插入同步队列时，如果没有头指针会自动初始化一个头指针，所以第一个插入的节点不会有问题<br>2.该节点的前驱节点是头节点，则当前结点获取到资源，并把自己设置为头指针，failed变量标记为false（因为新的头指针不需要删除，这样就把旧的头节点出队了）<br>3.超出资源限制的请求数量，throw new Error(“Maximum lock count exceeded”)，取消该node<br>cancelAcquire方法会将当前结点标记为取消状态，并且迭代移除当前结点的已取消的前驱节点知道第一个非取消状态的节点<br>主要操作是<br>1.当前是尾节点，删除当前结点更新尾节点<br>2.前驱节点不是头节点（因为头节点是标记节点要特殊处理），删除当前结点<br>3.前驱节点是头节点，调用unParkSuccess去唤起后一个线程（因为他没有获取到资源又是第一个节点不执行release）</p>
<p>而被标记为取消的节点在shouldParkAfterFailedAcquire中会被删除<br>因为Park下一个节点，他不是head下的第一个节点所以他会请求失败并执行shouldParkAfterFailedAcquire<br><figure class="highlight bash"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br></pre></td><td class="code"><pre><span class="line">private static boolean shouldParkAfterFailedAcquire(Node pred, Node node) &#123;</span><br><span class="line">        int ws = pred.waitStatus;</span><br><span class="line">        <span class="keyword">if</span> (ws == Node.SIGNAL)</span><br><span class="line">            /*</span><br><span class="line">             * This node has already <span class="built_in">set</span> status asking a release</span><br><span class="line">             * to signal it, so it can safely park.</span><br><span class="line">             */</span><br><span class="line">            <span class="built_in">return</span> <span class="literal">true</span>;</span><br><span class="line">        <span class="keyword">if</span> (ws &gt; 0) &#123;</span><br><span class="line">            /*</span><br><span class="line">             * Predecessor was cancelled. Skip over predecessors and</span><br><span class="line">             * indicate retry.</span><br><span class="line">             */</span><br><span class="line">            <span class="keyword">do</span> &#123;</span><br><span class="line">                node.prev = pred = pred.prev;</span><br><span class="line">            &#125; <span class="keyword">while</span> (pred.waitStatus &gt; 0);</span><br><span class="line">            pred.next = node;</span><br><span class="line">        &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">            /*</span><br><span class="line">             * waitStatus must be 0 or PROPAGATE.  Indicate that we</span><br><span class="line">             * need a signal, but don<span class="string">'t park yet.  Caller will need to</span></span><br><span class="line"><span class="string">             * retry to make sure it cannot acquire before parking.</span></span><br><span class="line"><span class="string">             */</span></span><br><span class="line"><span class="string">            compareAndSetWaitStatus(pred, ws, Node.SIGNAL);</span></span><br><span class="line"><span class="string">        &#125;</span></span><br><span class="line"><span class="string">        return false;</span></span><br><span class="line"><span class="string">    &#125;</span></span><br></pre></td></tr></table></figure></p>
<h3 id="请移步"><a href="#请移步" class="headerlink" title="请移步"></a>请移步</h3><p>个人主页: <a href="http://yangyitao.top" target="_blank" rel="noopener">yangyitao.top</a></p>

      
    </div>
    
    <div class="article-info article-info-index">
      
      
      

      
      <div class="clearfix"></div>
    </div>
      
    
  </div>
  
</article>







  
    <article id="post-并发基石-Markword与锁升级" class="article article-type-post" itemscope itemprop="blogPost">
  
    <div class="article-meta">
      <a href="/blog/2019/03/24/并发基石-Markword与锁升级/" class="article-date">
  	<time datetime="2019-03-24T04:17:57.599Z" itemprop="datePublished">2019-03-24</time>
</a>
    </div>
  
  <div class="article-inner">
    
      <input type="hidden" class="isFancy" />
    
    
      <header class="article-header">
        
  
    <h1 itemprop="name">
      <a class="article-title" href="/blog/2019/03/24/并发基石-Markword与锁升级/">
        并发基石-Markword与锁升级
        
      </a>
    </h1>
  

      </header>
      
    
    <div class="article-entry" itemprop="articleBody">
      
        <p>欢迎查看Eetal的第十一篇博客–并发基石-Markword与锁升级</p>
<h2 id="synchronized"><a href="#synchronized" class="headerlink" title="synchronized"></a>synchronized</h2><p>synchronized关键字是java提供的互斥锁关键字，我们常说的互斥锁一般都是非自旋锁，即竞争不到锁的线程会进入阻塞状态知道被唤醒<br>今天我们来讲讲java中用来对synchronized进行优化的三种锁，同时会介绍markword对象头<br>目前我在网上搜到的十几篇博客讲的都有问题,可能有写对的我没搜到.<br>很多人不经过验证直接把markOop.hpp中的JavaThread*当成ThreadId这是错误的，实际是java线程在C语言的指针<br>并且未计算过hashCode和计算过hashCode的情况也是不一样的<br>本篇博客最后会展示使用jol工具，读取展示对象头的结果进行验证<br>附上openjdk的markOop.hpp<a href="http://hg.openjdk.java.net/jdk8/jdk8/hotspot/file/87ee5ee27509/src/share/vm/oops/markOop.hpp" target="_blank" rel="noopener">链接</a></p>
<h2 id="对象头Markword"><a href="#对象头Markword" class="headerlink" title="对象头Markword"></a>对象头Markword</h2><p>对象头是java将对象比较常用和重要的运行时数据，如hashCode、gc标识、存活年龄等等进行集中存储的一组数据<br>占据8个字节，以下只讨论目前比较常见的64位的情况</p>
<h2 id="偏向锁、轻量级锁、重量级锁介绍"><a href="#偏向锁、轻量级锁、重量级锁介绍" class="headerlink" title="偏向锁、轻量级锁、重量级锁介绍"></a>偏向锁、轻量级锁、重量级锁介绍</h2><p>64bit下各锁状态的Markword格式<br><figure class="highlight bash"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br></pre></td><td class="code"><pre><span class="line">64 bits:</span><br><span class="line">  --------</span><br><span class="line">  unused:25 <span class="built_in">hash</span>:31 --&gt;| unused:1   age:4    biased_lock:1 lock:2 (normal object)</span><br><span class="line">  JavaThread*:54 epoch:2 unused:1   age:4    biased_lock:1 lock:2 (biased object)</span><br><span class="line">  PromotedObject*:61 ---------------------&gt;| promo_bits:3 -----&gt;| (CMS promoted object)</span><br><span class="line">  size:64 -----------------------------------------------------&gt;| (CMS free block)</span><br><span class="line"> </span><br><span class="line">  unused:25 <span class="built_in">hash</span>:31 --&gt;| cms_free:1 age:4    biased_lock:1 lock:2 (COOPs &amp;&amp; normal object)</span><br><span class="line">  JavaThread*:54 epoch:2 cms_free:1 age:4    biased_lock:1 lock:2 (COOPs &amp;&amp; biased object)</span><br><span class="line">  narrowOop:32 unused:24 cms_free:1 unused:4 promo_bits:3 -----&gt;| (COOPs &amp;&amp; CMS promoted object)</span><br><span class="line">  unused:21 size:35 --&gt;| cms_free:1 unused:7 ------------------&gt;| (COOPs &amp;&amp; CMS free block)</span><br><span class="line"> [ptr             | 00]  locked             ptr points to real header on stack</span><br><span class="line"> [header      | 0 | 01]  unlocked           regular object header</span><br><span class="line"> [ptr             | 10]  monitor            inflated lock (header is wapped out)</span><br><span class="line"> [ptr             | 11]  marked             used by markSweep to mark an object</span><br></pre></td></tr></table></figure></p>
<p>32bit下各锁状态的Markword格式<br><figure class="highlight bash"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></td><td class="code"><pre><span class="line">32 bits:</span><br><span class="line">  --------</span><br><span class="line">  <span class="built_in">hash</span>:25 ------------&gt;| age:4    biased_lock:1 lock:2 (normal object)</span><br><span class="line">  JavaThread*:23 epoch:2 age:4    biased_lock:1 lock:2 (biased object)</span><br><span class="line">  size:32 ------------------------------------------&gt;| (CMS free block)</span><br><span class="line">  PromotedObject*:29 ----------&gt;| promo_bits:3 -----&gt;| (CMS promoted object)</span><br></pre></td></tr></table></figure></p>
<p>也就是对象头的最后两位，是作为锁的状态标志<br>00—轻量锁<br>01—偏向锁/无锁<br>10—重量锁<br>11—GC标记<br>偏向锁状态和无锁状态通过区分对象头倒数第三位来确定，0代表无锁，1代表偏向锁<br>注意，未计算hashCode的对象的初始状态为匿名偏向锁（线程指针为0，代表无线程获取）而非无锁</p>
<h3 id="偏向锁与无锁"><a href="#偏向锁与无锁" class="headerlink" title="偏向锁与无锁"></a>偏向锁与无锁</h3><p>java中对于锁的实际获取依赖于UnSafe调用native方法去实现不同操作系统上的cas原语操作<br>如果一个对象，在每次作业的运行始终处于单一线程，那每次对于锁的检测、获取和释放都会对性能造成不小的消耗<br>于是java引入了偏向锁<br>当一个处于匿名偏向锁状态的对象，第一次被一个线程竞争时,其对象头会被标记为偏向锁,同时存储其线程指针<br>接下来每次该线程对该锁的获取都不需要经过不必要的cas判断锁资源从而优化了性能，这也是偏向的由来</p>
<p>匿名偏向锁状态的对象如果计算了hashCode，则会变为无锁状态。hashCode存在markword，并且接下来不会再进去偏向锁</p>
<p>匿名偏向锁状态的对象被获取时，进入非匿名偏向锁状态，markword存储持有者的java线程在操作系统的C语言指针</p>
<p>无锁状态下的对象被获取时，会直接跳到轻量级锁（因为偏向锁下markword没有记录hashCode，没办法存储hashCode,而轻量级锁的下面讲）</p>
<p>非匿名偏向锁状态的对象计算了hashCode以后,会直接进入重量级锁，此时的重量级锁会（重量级锁的下面讲）</p>
<p>开启偏向锁的支持需要添加两个虚拟机参数<br><figure class="highlight bash"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">-XX:+UseBiasedLocking</span><br><span class="line">-XX:BiasedLockingStartupDelay=0</span><br></pre></td></tr></table></figure></p>
<p>第一个参数是开启偏向锁<br>第二个参数是指定立即开启，因为默认偏向锁的开启时在虚拟机运行后延时5秒<br>如果没有线程竞争，非匿名偏向锁偏向锁释放后会变回匿名偏向锁状态</p>
<h3 id="锁升级-轻量级锁"><a href="#锁升级-轻量级锁" class="headerlink" title="锁升级-轻量级锁"></a>锁升级-轻量级锁</h3><p>当一个对象处于非匿名偏向锁状态下，如果有别的线程过来竞争，另一个线程尝试竞争锁，竞争失败并给予jvm一个竞争的信号以后进入自旋（不断尝试获取锁）<br>接下来在持有该锁的线程执行来到安全点时，会触发stop the world并将膨胀为轻量级锁<br>轻量级锁会创建一份锁记录(Lock Record)在当前持有他的线程的线程栈里<br>LockRecord中包含一个owner属性指向锁对象，而锁对象的markword中也会保存一个执行该LockRecord的指针</p>
<p>这时的竞争就是轻量级锁的竞争了，轻量级锁的竞争时，竞争锁的线程会在一个周期时间内不断的自旋获取锁，如果获取失败就会进入阻塞并将markword的锁标记标记为10（重量级锁）</p>
<p>因为LockRecord复制了markword，所以在执行同步块时并不去关注markword，只有到了释放时</p>
<p>1.锁对象的markword升级为了重量级锁，将锁对象升级为重量级锁，锁对象的markword存储一个指向一个由操作系统实现的mutex互斥变量，唤醒阻塞的竞争线程</p>
<p>2.markword没变化，释放锁，对象锁恢复到无锁状态（如果LockRecord记录的是偏向锁，则恢复到匿名偏向锁，否则恢复到无锁状态）</p>
<h2 id="锁升级-重量级锁"><a href="#锁升级-重量级锁" class="headerlink" title="锁升级-重量级锁"></a>锁升级-重量级锁</h2><p>当对象来到重量级锁以后，新被从竞争队列挑选出来一部分竞争锁的线程队列会一起竞争锁<br>最终竞争到锁的一个线程会继续运行，竞争失败的线程进入阻塞队列<br>处于执行状态的线程执行完同步代码块后，会释放锁并唤醒阻塞队列中的线程<br>将他们加入新的挑选出来的竞争锁的线程队列，并重新竞争锁，重复以上操作<br>因为需要阻塞和唤醒线程，所以需要从用户态到系统态切换，所以重量级锁下的系统开销很大</p>
<h2 id="代码验证"><a href="#代码验证" class="headerlink" title="代码验证"></a>代码验证</h2><figure class="highlight bash"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br></pre></td><td class="code"><pre><span class="line">Thread currentThread = Thread.currentThread();</span><br><span class="line">System.out.println(<span class="string">"threadId : "</span>+Long.toBinaryString(currentThread.getId()));</span><br><span class="line">Object o = new Object();</span><br><span class="line">System.out.println(<span class="string">"-------------------------------------------------------------------------------------------------------"</span>);</span><br><span class="line">System.out.println(<span class="string">"init object info"</span>);</span><br><span class="line">System.out.println(ClassLayout.parseInstance(o).toPrintable());</span><br><span class="line">System.out.println(<span class="string">"-------------------------------------------------------------------------------------------------------"</span>);</span><br><span class="line">synchronized (o) &#123;</span><br><span class="line">	System.out.println(<span class="string">"synchronized lock object info"</span>);</span><br><span class="line">	System.out.println(ClassLayout.parseInstance(o).toPrintable());</span><br><span class="line">	System.out.println(<span class="string">"synchronized finished"</span>);</span><br><span class="line">	System.out.println(<span class="string">"-------------------------------------------------------------------------------------------------------"</span>);</span><br><span class="line">&#125;</span><br><span class="line">Thread.sleep(2000);</span><br><span class="line">System.out.println(<span class="string">"after synchronized object info"</span>);</span><br><span class="line">System.out.println(ClassLayout.parseInstance(o).toPrintable());</span><br><span class="line">System.out.println(<span class="string">"binary hashCode : "</span>+Integer.toBinaryString(o.hashCode()));</span><br><span class="line">System.out.println(<span class="string">"-------------------------------------------------------------------------------------------------------"</span>);</span><br><span class="line"></span><br><span class="line">System.out.println(<span class="string">"after calculate hashcode object info"</span>);</span><br><span class="line">System.out.println(ClassLayout.parseInstance(o).toPrintable());</span><br><span class="line">System.out.println(<span class="string">"-------------------------------------------------------------------------------------------------------"</span>);</span><br><span class="line"></span><br><span class="line">synchronized (o) &#123;</span><br><span class="line">	System.out.println(<span class="string">"synchronized lock object info"</span>);</span><br><span class="line">	System.out.println(ClassLayout.parseInstance(o).toPrintable());</span><br><span class="line">	System.out.println(<span class="string">"synchronized finished"</span>);</span><br><span class="line">	System.out.println(<span class="string">"-------------------------------------------------------------------------------------------------------"</span>);</span><br><span class="line">&#125;</span><br><span class="line">Object o2 = new Object();</span><br><span class="line">System.out.println(<span class="string">"o2 hashCode : "</span>+Long.toBinaryString(o2.hashCode()));</span><br><span class="line">System.out.println(<span class="string">"init lock object2 info"</span>);</span><br><span class="line">System.out.println(ClassLayout.parseInstance(o2).toPrintable());</span><br><span class="line">System.out.println(<span class="string">"-------------------------------------------------------------------------------------------------------"</span>);</span><br><span class="line">synchronized (o2) &#123;</span><br><span class="line">	System.out.println(<span class="string">"synchronized lock object2 info"</span>);</span><br><span class="line">	System.out.println(ClassLayout.parseInstance(o2).toPrintable());</span><br><span class="line">	System.out.println(<span class="string">"synchronized finished"</span>);</span><br><span class="line">	System.out.println(<span class="string">"-------------------------------------------------------------------------------------------------------"</span>);</span><br><span class="line">&#125;</span><br><span class="line">System.out.println(<span class="string">"after lock object2 info"</span>);</span><br><span class="line">System.out.println(ClassLayout.parseInstance(o2).toPrintable());</span><br><span class="line">System.out.println(<span class="string">"-------------------------------------------------------------------------------------------------------"</span>);</span><br><span class="line">//计算过hashcode的会直接进入轻量锁</span><br></pre></td></tr></table></figure>
<p>输出结果<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br></pre></td><td class="code"><pre><span class="line">threadId : 1</span><br><span class="line">-------------------------------------------------------------------------------------------------------</span><br><span class="line">init object info</span><br><span class="line">java.lang.Object object internals:</span><br><span class="line"> OFFSET  SIZE   TYPE DESCRIPTION                               VALUE</span><br><span class="line">      0     4        (object header)                           05 00 00 00 (00000101 00000000 00000000 00000000) (5)</span><br><span class="line">      4     4        (object header)                           00 00 00 00 (00000000 00000000 00000000 00000000) (0)</span><br><span class="line">      8     4        (object header)                           e5 01 00 20 (11100101 00000001 00000000 00100000) (536871397)</span><br><span class="line">     12     4        (loss due to the next object alignment)</span><br><span class="line">Instance size: 16 bytes</span><br><span class="line">Space losses: 0 bytes internal + 4 bytes external = 4 bytes total</span><br><span class="line"></span><br><span class="line">-------------------------------------------------------------------------------------------------------</span><br><span class="line">synchronized lock object info</span><br><span class="line">java.lang.Object object internals:</span><br><span class="line"> OFFSET  SIZE   TYPE DESCRIPTION                               VALUE</span><br><span class="line">      0     4        (object header)                           05 e8 09 01 (00000101 11101000 00001001 00000001) (17426437)</span><br><span class="line">      4     4        (object header)                           00 00 00 00 (00000000 00000000 00000000 00000000) (0)</span><br><span class="line">      8     4        (object header)                           e5 01 00 20 (11100101 00000001 00000000 00100000) (536871397)</span><br><span class="line">     12     4        (loss due to the next object alignment)</span><br><span class="line">Instance size: 16 bytes</span><br><span class="line">Space losses: 0 bytes internal + 4 bytes external = 4 bytes total</span><br><span class="line"></span><br><span class="line">synchronized finished</span><br><span class="line">-------------------------------------------------------------------------------------------------------</span><br><span class="line">after synchronized object info</span><br><span class="line">java.lang.Object object internals:</span><br><span class="line"> OFFSET  SIZE   TYPE DESCRIPTION                               VALUE</span><br><span class="line">      0     4        (object header)                           05 e8 09 01 (00000101 11101000 00001001 00000001) (17426437)</span><br><span class="line">      4     4        (object header)                           00 00 00 00 (00000000 00000000 00000000 00000000) (0)</span><br><span class="line">      8     4        (object header)                           e5 01 00 20 (11100101 00000001 00000000 00100000) (536871397)</span><br><span class="line">     12     4        (loss due to the next object alignment)</span><br><span class="line">Instance size: 16 bytes</span><br><span class="line">Space losses: 0 bytes internal + 4 bytes external = 4 bytes total</span><br><span class="line"></span><br><span class="line">binary hashCode : 100000111110100010001111000001</span><br><span class="line">-------------------------------------------------------------------------------------------------------</span><br><span class="line">after calculate hashcode object info</span><br><span class="line">java.lang.Object object internals:</span><br><span class="line"> OFFSET  SIZE   TYPE DESCRIPTION                               VALUE</span><br><span class="line">      0     4        (object header)                           01 c1 23 fa (00000001 11000001 00100011 11111010) (-98320127)</span><br><span class="line">      4     4        (object header)                           20 00 00 00 (00100000 00000000 00000000 00000000) (32)</span><br><span class="line">      8     4        (object header)                           e5 01 00 20 (11100101 00000001 00000000 00100000) (536871397)</span><br><span class="line">     12     4        (loss due to the next object alignment)</span><br><span class="line">Instance size: 16 bytes</span><br><span class="line">Space losses: 0 bytes internal + 4 bytes external = 4 bytes total</span><br><span class="line"></span><br><span class="line">-------------------------------------------------------------------------------------------------------</span><br><span class="line">synchronized lock object info</span><br><span class="line">java.lang.Object object internals:</span><br><span class="line"> OFFSET  SIZE   TYPE DESCRIPTION                               VALUE</span><br><span class="line">      0     4        (object header)                           50 f7 c4 02 (01010000 11110111 11000100 00000010) (46462800)</span><br><span class="line">      4     4        (object header)                           00 00 00 00 (00000000 00000000 00000000 00000000) (0)</span><br><span class="line">      8     4        (object header)                           e5 01 00 20 (11100101 00000001 00000000 00100000) (536871397)</span><br><span class="line">     12     4        (loss due to the next object alignment)</span><br><span class="line">Instance size: 16 bytes</span><br><span class="line">Space losses: 0 bytes internal + 4 bytes external = 4 bytes total</span><br><span class="line"></span><br><span class="line">synchronized finished</span><br><span class="line">-------------------------------------------------------------------------------------------------------</span><br><span class="line">o2 hashCode : 110101100000011100010111110011</span><br><span class="line">init lock object2 info</span><br><span class="line">java.lang.Object object internals:</span><br><span class="line"> OFFSET  SIZE   TYPE DESCRIPTION                               VALUE</span><br><span class="line">      0     4        (object header)                           01 f3 c5 81 (00000001 11110011 11000101 10000001) (-2117733631)</span><br><span class="line">      4     4        (object header)                           35 00 00 00 (00110101 00000000 00000000 00000000) (53)</span><br><span class="line">      8     4        (object header)                           e5 01 00 20 (11100101 00000001 00000000 00100000) (536871397)</span><br><span class="line">     12     4        (loss due to the next object alignment)</span><br><span class="line">Instance size: 16 bytes</span><br><span class="line">Space losses: 0 bytes internal + 4 bytes external = 4 bytes total</span><br><span class="line"></span><br><span class="line">-------------------------------------------------------------------------------------------------------</span><br><span class="line">synchronized lock object2 info</span><br><span class="line">java.lang.Object object internals:</span><br><span class="line"> OFFSET  SIZE   TYPE DESCRIPTION                               VALUE</span><br><span class="line">      0     4        (object header)                           50 f7 c4 02 (01010000 11110111 11000100 00000010) (46462800)</span><br><span class="line">      4     4        (object header)                           00 00 00 00 (00000000 00000000 00000000 00000000) (0)</span><br><span class="line">      8     4        (object header)                           e5 01 00 20 (11100101 00000001 00000000 00100000) (536871397)</span><br><span class="line">     12     4        (loss due to the next object alignment)</span><br><span class="line">Instance size: 16 bytes</span><br><span class="line">Space losses: 0 bytes internal + 4 bytes external = 4 bytes total</span><br><span class="line"></span><br><span class="line">synchronized finished</span><br><span class="line">-------------------------------------------------------------------------------------------------------</span><br><span class="line">after lock object2 info</span><br><span class="line">java.lang.Object object internals:</span><br><span class="line"> OFFSET  SIZE   TYPE DESCRIPTION                               VALUE</span><br><span class="line">      0     4        (object header)                           01 f3 c5 81 (00000001 11110011 11000101 10000001) (-2117733631)</span><br><span class="line">      4     4        (object header)                           35 00 00 00 (00110101 00000000 00000000 00000000) (53)</span><br><span class="line">      8     4        (object header)                           e5 01 00 20 (11100101 00000001 00000000 00100000) (536871397)</span><br><span class="line">     12     4        (loss due to the next object alignment)</span><br><span class="line">Instance size: 16 bytes</span><br><span class="line">Space losses: 0 bytes internal + 4 bytes external = 4 bytes total</span><br><span class="line"></span><br><span class="line">-------------------------------------------------------------------------------------------------------</span><br></pre></td></tr></table></figure></p>
<p>多线程竞争<br><figure class="highlight bash"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br></pre></td><td class="code"><pre><span class="line">Thread currentThread = Thread.currentThread();</span><br><span class="line">		System.out.println(<span class="string">"threadId : "</span>+Long.toBinaryString(currentThread.getId()));</span><br><span class="line">		Object o = new Object();</span><br><span class="line">		System.out.println(<span class="string">"-------------------------------------------------------------------------------------------------------"</span>);</span><br><span class="line">		System.out.println(<span class="string">"init object info"</span>);</span><br><span class="line">		System.out.println(ClassLayout.parseInstance(o).toPrintable());</span><br><span class="line">		System.out.println(<span class="string">"-------------------------------------------------------------------------------------------------------"</span>);</span><br><span class="line">		</span><br><span class="line">		new <span class="function"><span class="title">Thread</span></span>() &#123;</span><br><span class="line">			public void <span class="function"><span class="title">run</span></span>() &#123;</span><br><span class="line">				synchronized (o) &#123;</span><br><span class="line">					System.out.println(<span class="string">"-------------------------------------------------------------------------------------------------------"</span>);</span><br><span class="line">					System.out.println(<span class="string">"-------------------------------------------------------------------------------------------------------"</span>);</span><br><span class="line">					System.out.println(<span class="string">"another thread id "</span>+Long.toBinaryString(this.getId()));</span><br><span class="line">					System.out.println(<span class="string">"synchronized lock object info"</span>);</span><br><span class="line">					System.out.println(ClassLayout.parseInstance(o).toPrintable());</span><br><span class="line">					System.out.println(<span class="string">"synchronized finished"</span>);</span><br><span class="line">					System.out.println(<span class="string">"-------------------------------------------------------------------------------------------------------"</span>);</span><br><span class="line">					System.out.println(<span class="string">"------------------------------------------------------------------------------------------------------"</span>);</span><br><span class="line">				&#125;</span><br><span class="line">			&#125;</span><br><span class="line">		&#125;.start();</span><br><span class="line">		</span><br><span class="line">		synchronized (o) &#123;</span><br><span class="line">			System.out.println(<span class="string">"synchronized lock object info"</span>);</span><br><span class="line">			System.out.println(ClassLayout.parseInstance(o).toPrintable());</span><br><span class="line">			</span><br><span class="line">			//有锁未计算hashCode状态下计算hashCode</span><br><span class="line">			</span><br><span class="line">			o.hashCode();</span><br><span class="line">			System.out.println(<span class="string">"when synchronized calculate hashcode "</span>);</span><br><span class="line">			System.out.println(ClassLayout.parseInstance(o).toPrintable());</span><br><span class="line">			</span><br><span class="line">			System.out.println(<span class="string">"synchronized finished"</span>);</span><br><span class="line">			System.out.println(<span class="string">"-------------------------------------------------------------------------------------------------------"</span>);</span><br><span class="line">		&#125;</span><br><span class="line">		Thread.sleep(2000);</span><br><span class="line">		System.out.println(<span class="string">"after synchronized object info"</span>);</span><br><span class="line">		System.out.println(ClassLayout.parseInstance(o).toPrintable());</span><br><span class="line">		System.out.println(<span class="string">"binary hashCode : "</span>+Integer.toBinaryString(o.hashCode()));</span><br><span class="line">		System.out.println(<span class="string">"-------------------------------------------------------------------------------------------------------"</span>);</span><br><span class="line">		</span><br><span class="line">		System.out.println(<span class="string">"after calculate hashcode object info"</span>);</span><br><span class="line">		System.out.println(ClassLayout.parseInstance(o).toPrintable());</span><br><span class="line">		System.out.println(<span class="string">"-------------------------------------------------------------------------------------------------------"</span>);</span><br><span class="line">		</span><br><span class="line">		synchronized (o) &#123;</span><br><span class="line">			System.out.println(<span class="string">"synchronized lock object info"</span>);</span><br><span class="line">			System.out.println(ClassLayout.parseInstance(o).toPrintable());</span><br><span class="line">			System.out.println(<span class="string">"synchronized finished"</span>);</span><br><span class="line">			System.out.println(<span class="string">"-------------------------------------------------------------------------------------------------------"</span>);</span><br><span class="line">		&#125;</span><br><span class="line">		Object o2 = new Object();</span><br><span class="line">		System.out.println(<span class="string">"o2 hashCode : "</span>+Long.toBinaryString(o2.hashCode()));</span><br><span class="line">		System.out.println(<span class="string">"init lock object2 info"</span>);</span><br><span class="line">		System.out.println(ClassLayout.parseInstance(o2).toPrintable());</span><br><span class="line">		System.out.println(<span class="string">"-------------------------------------------------------------------------------------------------------"</span>);</span><br><span class="line">		synchronized (o2) &#123;</span><br><span class="line">			System.out.println(<span class="string">"synchronized lock object2 info"</span>);</span><br><span class="line">			System.out.println(ClassLayout.parseInstance(o2).toPrintable());</span><br><span class="line">			System.out.println(<span class="string">"synchronized finished"</span>);</span><br><span class="line">			System.out.println(<span class="string">"-------------------------------------------------------------------------------------------------------"</span>);</span><br><span class="line">		&#125;</span><br><span class="line">		System.out.println(<span class="string">"after lock object2 info"</span>);</span><br><span class="line">		System.out.println(ClassLayout.parseInstance(o2).toPrintable());</span><br><span class="line">		System.out.println(<span class="string">"-------------------------------------------------------------------------------------------------------"</span>);</span><br><span class="line">		//计算过hashcode的会直接进入轻量锁</span><br></pre></td></tr></table></figure></p>
<p>输出结果<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br><span class="line">109</span><br><span class="line">110</span><br><span class="line">111</span><br><span class="line">112</span><br><span class="line">113</span><br><span class="line">114</span><br><span class="line">115</span><br><span class="line">116</span><br><span class="line">117</span><br><span class="line">118</span><br><span class="line">119</span><br><span class="line">120</span><br><span class="line">121</span><br></pre></td><td class="code"><pre><span class="line">threadId : 1</span><br><span class="line">-------------------------------------------------------------------------------------------------------</span><br><span class="line">init object info</span><br><span class="line">java.lang.Object object internals:</span><br><span class="line"> OFFSET  SIZE   TYPE DESCRIPTION                               VALUE</span><br><span class="line">      0     4        (object header)                           05 00 00 00 (00000101 00000000 00000000 00000000) (5)</span><br><span class="line">      4     4        (object header)                           00 00 00 00 (00000000 00000000 00000000 00000000) (0)</span><br><span class="line">      8     4        (object header)                           e5 01 00 20 (11100101 00000001 00000000 00100000) (536871397)</span><br><span class="line">     12     4        (loss due to the next object alignment)</span><br><span class="line">Instance size: 16 bytes</span><br><span class="line">Space losses: 0 bytes internal + 4 bytes external = 4 bytes total</span><br><span class="line"></span><br><span class="line">-------------------------------------------------------------------------------------------------------</span><br><span class="line">synchronized lock object info</span><br><span class="line">java.lang.Object object internals:</span><br><span class="line"> OFFSET  SIZE   TYPE DESCRIPTION                               VALUE</span><br><span class="line">      0     4        (object header)                           ba c4 c4 02 (10111010 11000100 11000100 00000010) (46449850)</span><br><span class="line">      4     4        (object header)                           00 00 00 00 (00000000 00000000 00000000 00000000) (0)</span><br><span class="line">      8     4        (object header)                           e5 01 00 20 (11100101 00000001 00000000 00100000) (536871397)</span><br><span class="line">     12     4        (loss due to the next object alignment)</span><br><span class="line">Instance size: 16 bytes</span><br><span class="line">Space losses: 0 bytes internal + 4 bytes external = 4 bytes total</span><br><span class="line"></span><br><span class="line">when synchronized calculate hashcode </span><br><span class="line">java.lang.Object object internals:</span><br><span class="line"> OFFSET  SIZE   TYPE DESCRIPTION                               VALUE</span><br><span class="line">      0     4        (object header)                           ba c4 c4 02 (10111010 11000100 11000100 00000010) (46449850)</span><br><span class="line">      4     4        (object header)                           00 00 00 00 (00000000 00000000 00000000 00000000) (0)</span><br><span class="line">      8     4        (object header)                           e5 01 00 20 (11100101 00000001 00000000 00100000) (536871397)</span><br><span class="line">     12     4        (loss due to the next object alignment)</span><br><span class="line">Instance size: 16 bytes</span><br><span class="line">Space losses: 0 bytes internal + 4 bytes external = 4 bytes total</span><br><span class="line"></span><br><span class="line">synchronized finished</span><br><span class="line">-------------------------------------------------------------------------------------------------------</span><br><span class="line">-------------------------------------------------------------------------------------------------------</span><br><span class="line">-------------------------------------------------------------------------------------------------------</span><br><span class="line">another thread id 1010</span><br><span class="line">synchronized lock object info</span><br><span class="line">java.lang.Object object internals:</span><br><span class="line"> OFFSET  SIZE   TYPE DESCRIPTION                               VALUE</span><br><span class="line">      0     4        (object header)                           ba c4 c4 02 (10111010 11000100 11000100 00000010) (46449850)</span><br><span class="line">      4     4        (object header)                           00 00 00 00 (00000000 00000000 00000000 00000000) (0)</span><br><span class="line">      8     4        (object header)                           e5 01 00 20 (11100101 00000001 00000000 00100000) (536871397)</span><br><span class="line">     12     4        (loss due to the next object alignment)</span><br><span class="line">Instance size: 16 bytes</span><br><span class="line">Space losses: 0 bytes internal + 4 bytes external = 4 bytes total</span><br><span class="line"></span><br><span class="line">synchronized finished</span><br><span class="line">-------------------------------------------------------------------------------------------------------</span><br><span class="line">------------------------------------------------------------------------------------------------------</span><br><span class="line">after synchronized object info</span><br><span class="line">java.lang.Object object internals:</span><br><span class="line"> OFFSET  SIZE   TYPE DESCRIPTION                               VALUE</span><br><span class="line">      0     4        (object header)                           01 c1 23 fa (00000001 11000001 00100011 11111010) (-98320127)</span><br><span class="line">      4     4        (object header)                           20 00 00 00 (00100000 00000000 00000000 00000000) (32)</span><br><span class="line">      8     4        (object header)                           e5 01 00 20 (11100101 00000001 00000000 00100000) (536871397)</span><br><span class="line">     12     4        (loss due to the next object alignment)</span><br><span class="line">Instance size: 16 bytes</span><br><span class="line">Space losses: 0 bytes internal + 4 bytes external = 4 bytes total</span><br><span class="line"></span><br><span class="line">binary hashCode : 100000111110100010001111000001</span><br><span class="line">-------------------------------------------------------------------------------------------------------</span><br><span class="line">after calculate hashcode object info</span><br><span class="line">java.lang.Object object internals:</span><br><span class="line"> OFFSET  SIZE   TYPE DESCRIPTION                               VALUE</span><br><span class="line">      0     4        (object header)                           01 c1 23 fa (00000001 11000001 00100011 11111010) (-98320127)</span><br><span class="line">      4     4        (object header)                           20 00 00 00 (00100000 00000000 00000000 00000000) (32)</span><br><span class="line">      8     4        (object header)                           e5 01 00 20 (11100101 00000001 00000000 00100000) (536871397)</span><br><span class="line">     12     4        (loss due to the next object alignment)</span><br><span class="line">Instance size: 16 bytes</span><br><span class="line">Space losses: 0 bytes internal + 4 bytes external = 4 bytes total</span><br><span class="line"></span><br><span class="line">-------------------------------------------------------------------------------------------------------</span><br><span class="line">synchronized lock object info</span><br><span class="line">java.lang.Object object internals:</span><br><span class="line"> OFFSET  SIZE   TYPE DESCRIPTION                               VALUE</span><br><span class="line">      0     4        (object header)                           90 f5 ad 02 (10010000 11110101 10101101 00000010) (44955024)</span><br><span class="line">      4     4        (object header)                           00 00 00 00 (00000000 00000000 00000000 00000000) (0)</span><br><span class="line">      8     4        (object header)                           e5 01 00 20 (11100101 00000001 00000000 00100000) (536871397)</span><br><span class="line">     12     4        (loss due to the next object alignment)</span><br><span class="line">Instance size: 16 bytes</span><br><span class="line">Space losses: 0 bytes internal + 4 bytes external = 4 bytes total</span><br><span class="line"></span><br><span class="line">synchronized finished</span><br><span class="line">-------------------------------------------------------------------------------------------------------</span><br><span class="line">o2 hashCode : 110101100000011100010111110011</span><br><span class="line">init lock object2 info</span><br><span class="line">java.lang.Object object internals:</span><br><span class="line"> OFFSET  SIZE   TYPE DESCRIPTION                               VALUE</span><br><span class="line">      0     4        (object header)                           01 f3 c5 81 (00000001 11110011 11000101 10000001) (-2117733631)</span><br><span class="line">      4     4        (object header)                           35 00 00 00 (00110101 00000000 00000000 00000000) (53)</span><br><span class="line">      8     4        (object header)                           e5 01 00 20 (11100101 00000001 00000000 00100000) (536871397)</span><br><span class="line">     12     4        (loss due to the next object alignment)</span><br><span class="line">Instance size: 16 bytes</span><br><span class="line">Space losses: 0 bytes internal + 4 bytes external = 4 bytes total</span><br><span class="line"></span><br><span class="line">-------------------------------------------------------------------------------------------------------</span><br><span class="line">synchronized lock object2 info</span><br><span class="line">java.lang.Object object internals:</span><br><span class="line"> OFFSET  SIZE   TYPE DESCRIPTION                               VALUE</span><br><span class="line">      0     4        (object header)                           90 f5 ad 02 (10010000 11110101 10101101 00000010) (44955024)</span><br><span class="line">      4     4        (object header)                           00 00 00 00 (00000000 00000000 00000000 00000000) (0)</span><br><span class="line">      8     4        (object header)                           e5 01 00 20 (11100101 00000001 00000000 00100000) (536871397)</span><br><span class="line">     12     4        (loss due to the next object alignment)</span><br><span class="line">Instance size: 16 bytes</span><br><span class="line">Space losses: 0 bytes internal + 4 bytes external = 4 bytes total</span><br><span class="line"></span><br><span class="line">synchronized finished</span><br><span class="line">-------------------------------------------------------------------------------------------------------</span><br><span class="line">after lock object2 info</span><br><span class="line">java.lang.Object object internals:</span><br><span class="line"> OFFSET  SIZE   TYPE DESCRIPTION                               VALUE</span><br><span class="line">      0     4        (object header)                           01 f3 c5 81 (00000001 11110011 11000101 10000001) (-2117733631)</span><br><span class="line">      4     4        (object header)                           35 00 00 00 (00110101 00000000 00000000 00000000) (53)</span><br><span class="line">      8     4        (object header)                           e5 01 00 20 (11100101 00000001 00000000 00100000) (536871397)</span><br><span class="line">     12     4        (loss due to the next object alignment)</span><br><span class="line">Instance size: 16 bytes</span><br><span class="line">Space losses: 0 bytes internal + 4 bytes external = 4 bytes total</span><br><span class="line"></span><br><span class="line">-------------------------------------------------------------------------------------------------------</span><br></pre></td></tr></table></figure></p>
<h3 id="请移步"><a href="#请移步" class="headerlink" title="请移步"></a>请移步</h3><p>个人主页: <a href="http://yangyitao.top" target="_blank" rel="noopener">yangyitao.top</a></p>

      
    </div>
    
    <div class="article-info article-info-index">
      
      
      

      
      <div class="clearfix"></div>
    </div>
      
    
  </div>
  
</article>







  
    <article id="post-HashMap、TreeMap、HashTable、ConcurrentHashMap对比" class="article article-type-post" itemscope itemprop="blogPost">
  
    <div class="article-meta">
      <a href="/blog/2019/03/23/HashMap、TreeMap、HashTable、ConcurrentHashMap对比/" class="article-date">
  	<time datetime="2019-03-23T07:29:54.608Z" itemprop="datePublished">2019-03-23</time>
</a>
    </div>
  
  <div class="article-inner">
    
      <input type="hidden" class="isFancy" />
    
    
      <header class="article-header">
        
  
    <h1 itemprop="name">
      <a class="article-title" href="/blog/2019/03/23/HashMap、TreeMap、HashTable、ConcurrentHashMap对比/">
        HashMap、TreeMap、HashTable、ConcurrentHashMap对比(jdk1.8)
        
      </a>
    </h1>
  

      </header>
      
    
    <div class="article-entry" itemprop="articleBody">
      
        <p>欢迎查看Eetal的第十篇博客–HashMap、TreeMap、HashTable、ConcurrentHashMap对比(jdk1.8)</p>
<h2 id="HashMap"><a href="#HashMap" class="headerlink" title="HashMap"></a>HashMap</h2><p>HashMap是java中经常用来存取键值对形式的一个集合类<br>1.8以后实现方式为    数组(Node&lt;K,V&gt;[])+链表(Node)<br>首先计算出要存储的key应该到数组中哪个位置的链表下<br><figure class="highlight bash"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line">static final int <span class="built_in">hash</span>(Object key) &#123;</span><br><span class="line">       int h;</span><br><span class="line">       <span class="built_in">return</span> (key == null) ? 0 : (h = key.hashCode()) ^ (h &gt;&gt;&gt; 16);</span><br><span class="line">   &#125;</span><br></pre></td></tr></table></figure></p>
<p>静态方法hash将key的hashCode的高16位与低16位异或的值作为其hash值,异或是为了减少在map的hash数组长度较小时的hash碰撞，使其更均匀<br>如果key是null则为0，这也是为什么HashMap可以使用null作为key而ConcurrentHashMap不行的原因<br>在putVal方法中使用这个hash的值去与当前的数组大小求余计算出其位置</p>
<figure class="highlight bash"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br></pre></td><td class="code"><pre><span class="line">final V putVal(int <span class="built_in">hash</span>, K key, V value, boolean onlyIfAbsent,</span><br><span class="line">				   boolean evict) &#123;</span><br><span class="line">		Node&lt;K,V&gt;[] tab; Node&lt;K,V&gt; p; int n, i;</span><br><span class="line">		<span class="keyword">if</span> ((tab = table) == null || (n = tab.length) == 0)</span><br><span class="line">			n = (tab = resize()).length;</span><br><span class="line">		<span class="keyword">if</span> ((p = tab[i = (n - 1) &amp; <span class="built_in">hash</span>]) == null) //---计算数组位置</span><br><span class="line">			tab[i] = newNode(<span class="built_in">hash</span>, key, value, null);</span><br><span class="line">		<span class="keyword">else</span> &#123;</span><br><span class="line">			Node&lt;K,V&gt; e; K k;</span><br><span class="line">			<span class="keyword">if</span> (p.hash == <span class="built_in">hash</span> &amp;&amp;</span><br><span class="line">				((k = p.key) == key || (key != null &amp;&amp; key.equals(k))))</span><br><span class="line">				e = p;</span><br><span class="line">			<span class="keyword">else</span> <span class="keyword">if</span> (p instanceof TreeNode)</span><br><span class="line">				e = ((TreeNode&lt;K,V&gt;)p).putTreeVal(this, tab, <span class="built_in">hash</span>, key, value);</span><br><span class="line">			<span class="keyword">else</span> &#123;</span><br><span class="line">				<span class="keyword">for</span> (int binCount = 0; ; ++binCount) &#123;</span><br><span class="line">					<span class="keyword">if</span> ((e = p.next) == null) &#123;</span><br><span class="line">						p.next = newNode(<span class="built_in">hash</span>, key, value, null);</span><br><span class="line">						<span class="keyword">if</span> (binCount &gt;= TREEIFY_THRESHOLD - 1) // -1 <span class="keyword">for</span> 1st</span><br><span class="line">							treeifyBin(tab, <span class="built_in">hash</span>);</span><br><span class="line">						<span class="built_in">break</span>;</span><br><span class="line">					&#125;</span><br><span class="line">					<span class="keyword">if</span> (e.hash == <span class="built_in">hash</span> &amp;&amp;</span><br><span class="line">						((k = e.key) == key || (key != null &amp;&amp; key.equals(k))))</span><br><span class="line">						<span class="built_in">break</span>;</span><br><span class="line">					p = e;</span><br><span class="line">				&#125;</span><br><span class="line">			&#125;</span><br><span class="line">			<span class="keyword">if</span> (e != null) &#123; // existing mapping <span class="keyword">for</span> key</span><br><span class="line">				V oldValue = e.value;</span><br><span class="line">				<span class="keyword">if</span> (!onlyIfAbsent || oldValue == null)</span><br><span class="line">					e.value = value;</span><br><span class="line">				afterNodeAccess(e);</span><br><span class="line">				<span class="built_in">return</span> oldValue;</span><br><span class="line">			&#125;</span><br><span class="line">		&#125;</span><br><span class="line">		++modCount;</span><br><span class="line">		<span class="keyword">if</span> (++size &gt; threshold)</span><br><span class="line">			resize();</span><br><span class="line">		afterNodeInsertion(evict);</span><br><span class="line">		<span class="built_in">return</span> null;</span><br><span class="line">	&#125;</span><br></pre></td></tr></table></figure>
<h2 id="重要参数"><a href="#重要参数" class="headerlink" title="重要参数"></a>重要参数</h2><figure class="highlight bash"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br></pre></td><td class="code"><pre><span class="line">static final int DEFAULT_INITIAL_CAPACITY = 1 &lt;&lt; 4; // aka 16</span><br><span class="line"></span><br><span class="line">/**</span><br><span class="line"> * The maximum capacity, used <span class="keyword">if</span> a higher value is implicitly specified</span><br><span class="line"> * by either of the constructors with arguments.</span><br><span class="line"> * MUST be a power of two &lt;= 1&lt;&lt;30.</span><br><span class="line"> */</span><br><span class="line">static final int MAXIMUM_CAPACITY = 1 &lt;&lt; 30;</span><br><span class="line"></span><br><span class="line">/**</span><br><span class="line"> * The load factor used when none specified <span class="keyword">in</span> constructor.</span><br><span class="line"> */</span><br><span class="line">static final <span class="built_in">float</span> DEFAULT_LOAD_FACTOR = 0.75f;</span><br></pre></td></tr></table></figure>
<h2 id="重要构造函数"><a href="#重要构造函数" class="headerlink" title="重要构造函数"></a>重要构造函数</h2><p>hashmap限制容量CAPACITY为2的幂，每次扩容为乘以2,这样可以保证数据的均匀分布，同时使得hashmap只有resize方法而不需要rehash,下面详谈<br>第一个DEFAULT_INITIAL_CAPACITY默认的数组大小，也就是不指定时默认开辟的hash数组大小为2的4次方<br>第二个MAXIMUM_CAPACITY，最大扩容至的hash数组大小,如果指定的数组大小大于这个值，会被替换为这个值,原因是,数组的下表要求是int类型,而int在java中是4个字节,共32位，而第一位表示符号位，因此可以表示的最大2的幂为2的30次方<br>最后DEFAULT_LOAD_FACTOR代表负载因子,当put操作以后 map的size &gt; hash数组的长度*负载因子时,就会触发扩容，<br>当然hashmap提供了指定initialCapacity的构造函数,但在1.8里，这个参数并不会改变其capacity，只会改变threshold的值以下为源码<br><figure class="highlight bash"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br></pre></td><td class="code"><pre><span class="line">/**</span><br><span class="line">    * Constructs an empty &lt;tt&gt;HashMap&lt;/tt&gt; with the specified initial</span><br><span class="line">    * capacity and load factor.</span><br><span class="line">    *</span><br><span class="line">    * @param  initialCapacity the initial capacity</span><br><span class="line">    * @param  loadFactor      the load factor</span><br><span class="line">    * @throws IllegalArgumentException <span class="keyword">if</span> the initial capacity is negative</span><br><span class="line">    *         or the load factor is nonpositive</span><br><span class="line">    */</span><br><span class="line">   public HashMap(int initialCapacity, <span class="built_in">float</span> loadFactor) &#123;</span><br><span class="line">       <span class="keyword">if</span> (initialCapacity &lt; 0)</span><br><span class="line">           throw new IllegalArgumentException(<span class="string">"Illegal initial capacity: "</span> +</span><br><span class="line">                                              initialCapacity);</span><br><span class="line">       <span class="keyword">if</span> (initialCapacity &gt; MAXIMUM_CAPACITY)</span><br><span class="line">           initialCapacity = MAXIMUM_CAPACITY;</span><br><span class="line">       <span class="keyword">if</span> (loadFactor &lt;= 0 || Float.isNaN(loadFactor))</span><br><span class="line">           throw new IllegalArgumentException(<span class="string">"Illegal load factor: "</span> +</span><br><span class="line">                                              loadFactor);</span><br><span class="line">       this.loadFactor = loadFactor;</span><br><span class="line">       this.threshold = tableSizeFor(initialCapacity);</span><br><span class="line">   &#125;</span><br><span class="line"></span><br><span class="line">   /**</span><br><span class="line">    * Returns a power of two size <span class="keyword">for</span> the given target capacity.</span><br><span class="line">    */</span><br><span class="line">   static final int tableSizeFor(int <span class="built_in">cap</span>) &#123;</span><br><span class="line">       int n = <span class="built_in">cap</span> - 1;</span><br><span class="line">       n |= n &gt;&gt;&gt; 1;</span><br><span class="line">       n |= n &gt;&gt;&gt; 2;</span><br><span class="line">       n |= n &gt;&gt;&gt; 4;</span><br><span class="line">       n |= n &gt;&gt;&gt; 8;</span><br><span class="line">       n |= n &gt;&gt;&gt; 16;</span><br><span class="line">       <span class="built_in">return</span> (n &lt; 0) ? 1 : (n &gt;= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;</span><br><span class="line">   &#125;</span><br></pre></td></tr></table></figure></p>
<p>指定initialCapacity只能改变扩容时机，而并不改变hash数组长度</p>
<h2 id="put操作与resize"><a href="#put操作与resize" class="headerlink" title="put操作与resize"></a>put操作与resize</h2><p>put操作较简单，计算到对应Node,为null则新建,不为null则根据该Node类型为TreeNode还是普通Node执行不同的插入操作<br>当put以后，如果size大于threshold扩容时机，则进行扩容（数组长度乘以2）<br>同时进行rehash,此处源码使用了一个快捷的办法，因为数组的长度必定为2的倍数<br>假设长度为2的x次方,则旧hash数组第i个位置上的链表的所有Node的hash都应该为 Nj<em>(2的x次方)+i<br>因为新扩容的数组长度为原来的两倍(重点),则 长度为 2</em>(2的x次方)，此时进行resize<br>hash%(2<em>(2的x次方)) == (hash%(2的x次方))+(2的x次方)</em>(hash&amp;(2的x+1次方))<br>而hash%(2的x次方)为node所在旧hash数组下标i,oldCap为旧数组的长度，式子可写为<br>    新数组的位置下标 newI = i + oldCap * (hash &amp; oldCap)<br>官方实现代码如下,将旧数组每个位置上的链表拆分为高低两条新链表，分别代表hash &amp; oldCap为0和为1的节点<br>再把这两条链表对应到新数组的位置 newTab[j] 和 newTab[oldCap + j]</p>
<figure class="highlight bash"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br></pre></td><td class="code"><pre><span class="line">// j from 0 to oldCap-1</span><br><span class="line">Node&lt;K,V&gt; loHead = null, loTail = null;</span><br><span class="line">Node&lt;K,V&gt; hiHead = null, hiTail = null;</span><br><span class="line">Node&lt;K,V&gt; next;</span><br><span class="line"><span class="keyword">do</span> &#123;</span><br><span class="line">	next = e.next;</span><br><span class="line">	<span class="keyword">if</span> ((e.hash &amp; oldCap) == 0) &#123;</span><br><span class="line">		<span class="keyword">if</span> (loTail == null)</span><br><span class="line">			loHead = e;</span><br><span class="line">		<span class="keyword">else</span></span><br><span class="line">			loTail.next = e;</span><br><span class="line">		loTail = e;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">else</span> &#123;</span><br><span class="line">		<span class="keyword">if</span> (hiTail == null)</span><br><span class="line">			hiHead = e;</span><br><span class="line">		<span class="keyword">else</span></span><br><span class="line">			hiTail.next = e;</span><br><span class="line">		hiTail = e;</span><br><span class="line">	&#125;</span><br><span class="line">&#125; <span class="keyword">while</span> ((e = next) != null);</span><br><span class="line"><span class="keyword">if</span> (loTail != null) &#123;</span><br><span class="line">	loTail.next = null;</span><br><span class="line">	newTab[j] = loHead;</span><br><span class="line">&#125;</span><br><span class="line"><span class="keyword">if</span> (hiTail != null) &#123;</span><br><span class="line">	hiTail.next = null;</span><br><span class="line">	newTab[j + oldCap] = hiHead;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="HashMap死锁问题"><a href="#HashMap死锁问题" class="headerlink" title="HashMap死锁问题"></a>HashMap死锁问题</h2><p>因为HashMap中的put和remove都是不加对象锁的，也就是非线程安全的<br>且其table属性(hash数组的引用)也没有使用volatile修饰(修饰了也不能百分百解决并发问题,因此官方默认HashMap为非线程安全的map以提高其效率)<br>如果在resize的过程,另一个线程拿到的是oldTable，并对其进行如删除元素或新增元素<br>因为原有的单条链表hi拆分重新组建为高低两条链表，这期间对oldTable节点的插入和删除操作可能会导致把新构建的链表中的部分节点形成环(因为新链表的序列与oldTable原有不一样)<br>最终导致在get和put时，遍历链表时进入无限死循环<br>因此在多线程下应使用ConcurrentHashMap代替HashMap</p>
<h2 id="TreeMap"><a href="#TreeMap" class="headerlink" title="TreeMap"></a>TreeMap</h2><p>TreeMap为有序的map,本质是一条链表<br>可以在构造是传入一个比较器，或者每个元素的类都有实现Comparable接口<br>HashMap的插入为计算到数组位置后,添加到对应Node链表末端<br>TreeMap为比较计算位置后插入对应链表位置<br>在未传入比较器的情况下，key不允许为null</p>
<h2 id="简介ConcurrentHashMap和HashTable"><a href="#简介ConcurrentHashMap和HashTable" class="headerlink" title="简介ConcurrentHashMap和HashTable"></a>简介ConcurrentHashMap和HashTable</h2><p>HashTable为HashMap的线程安全版,其中会有线程安全问题的方法都采用使用this对象作为锁的方式来实现互斥<br>而ConcurrentHashMap1.5以前为使用分段锁，即双数组,原本存放Entry的地方改为存放segemant数组，代码1000多行<br>segemant对象继承了ReentrantLock，包含有一个与Entry数组的属性<br>插入和删除修改时,只锁被Hash到的segemant对象，再hash元素到segemant的Entry数组对应的位置，插入到对应位置链表中去<br>jdk1.5开始，Doug Lea 大牛改为和HashMap一样的Node结构,往类里注入了Unsafe对象<br>修改时只锁被hash到的对应的链表头指针Node，通过各种cas操作和synchronized检验和修改插入等操作<br>jdk1.5以后的ConcurrentHashMap的源码足足来到6312行，TQL，到处都是使用unsafe的cas和计算对象偏移来完成原语操作<br><figure class="highlight bash"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br></pre></td><td class="code"><pre><span class="line">   // Unsafe mechanics</span><br><span class="line">   private static final sun.misc.Unsafe U;</span><br><span class="line">   private static final long SIZECTL;</span><br><span class="line">   private static final long TRANSFERINDEX;</span><br><span class="line">   private static final long BASECOUNT;</span><br><span class="line">   private static final long CELLSBUSY;</span><br><span class="line">   private static final long CELLVALUE;</span><br><span class="line">   private static final long ABASE;</span><br><span class="line">   private static final int ASHIFT;</span><br><span class="line"></span><br><span class="line">   static &#123;</span><br><span class="line">       try &#123;</span><br><span class="line">           U = sun.misc.Unsafe.getUnsafe();</span><br><span class="line">		...</span><br><span class="line">		&#125;</span><br><span class="line">	...	</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<p>因此效率上而言ConcurrentHashMap会优于HashTable</p>
<h3 id="请移步"><a href="#请移步" class="headerlink" title="请移步"></a>请移步</h3><p>个人主页: <a href="http://yangyitao.top" target="_blank" rel="noopener">yangyitao.top</a></p>

      
    </div>
    
    <div class="article-info article-info-index">
      
      
      

      
      <div class="clearfix"></div>
    </div>
      
    
  </div>
  
</article>







  
    <article id="post-使用future机制和对象锁实现SynchronizedExecutor" class="article article-type-post" itemscope itemprop="blogPost">
  
    <div class="article-meta">
      <a href="/blog/2019/03/23/使用future机制和对象锁实现SynchronizedExecutor/" class="article-date">
  	<time datetime="2019-03-23T07:06:42.851Z" itemprop="datePublished">2019-03-23</time>
</a>
    </div>
  
  <div class="article-inner">
    
      <input type="hidden" class="isFancy" />
    
    
      <header class="article-header">
        
  
    <h1 itemprop="name">
      <a class="article-title" href="/blog/2019/03/23/使用future机制和对象锁实现SynchronizedExecutor/">
        使用future机制和对象锁实现SynchronizedExecutor
        
      </a>
    </h1>
  

      </header>
      
    
    <div class="article-entry" itemprop="articleBody">
      
        <p>欢迎查看Eetal的第九篇博客–使用future机制和对象锁实现SynchronizedExecutor</p>
<h2 id="future"><a href="#future" class="headerlink" title="future"></a>future</h2><p>future代表一个任务的预执行结果，通过get方法获取执行结果<br><figure class="highlight bash"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line">public interface Future&lt;V&gt; &#123;</span><br><span class="line">	V get() throws Exception;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<h2 id="callable"><a href="#callable" class="headerlink" title="callable"></a>callable</h2><p>callable代表一个要执行的任务，执行方法call，执行完成返回一个值<br><figure class="highlight bash"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line">public interface Callable&lt;V&gt; &#123;</span><br><span class="line">	V call() throws Exception;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<h2 id="executor"><a href="#executor" class="headerlink" title="executor"></a>executor</h2><p>executor为执行器，通过执行器来执行任务并得到预执行结果对象future<br><figure class="highlight bash"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line">public interface Executor&lt;V&gt; &#123;</span><br><span class="line">	Future&lt;V&gt; execute(Callable&lt;V&gt; callable);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<h2 id="SynchronizedExecutor"><a href="#SynchronizedExecutor" class="headerlink" title="SynchronizedExecutor"></a>SynchronizedExecutor<v></v></h2><p>使用synchronized关键字实现的执行器<br><figure class="highlight bash"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br></pre></td><td class="code"><pre><span class="line">public class SynchronizedExecutor&lt;V&gt; implements Executor&lt;V&gt; &#123;</span><br><span class="line">	</span><br><span class="line">	static class ExecutorThread&lt;V&gt; extends Thread&#123;</span><br><span class="line">		public Object lock;</span><br><span class="line">		public V result;</span><br><span class="line">		public Callable&lt;V&gt; task;</span><br><span class="line">		public Exception e;</span><br><span class="line">		public boolean isDone = <span class="literal">false</span>;</span><br><span class="line">		public ExecutorThread(Callable&lt;V&gt; task,Object lock) &#123;</span><br><span class="line">			this.lock = lock;</span><br><span class="line">			this.task = task;</span><br><span class="line">		&#125;</span><br><span class="line">		@Override</span><br><span class="line">		public void <span class="function"><span class="title">run</span></span>() &#123;</span><br><span class="line">			try &#123;</span><br><span class="line">				result = task.call();</span><br><span class="line">			&#125; catch (Exception e) &#123;</span><br><span class="line">				this.e = e;</span><br><span class="line">			&#125;finally &#123;</span><br><span class="line">				synchronized (lock) &#123;</span><br><span class="line">					//需持有锁才能调用notify</span><br><span class="line">					this.isDone = <span class="literal">true</span>;</span><br><span class="line">					lock.notifyAll();</span><br><span class="line">					//此处的加锁只是为了获得锁</span><br><span class="line">				&#125;</span><br><span class="line">			&#125;</span><br><span class="line">			</span><br><span class="line">		&#125;</span><br><span class="line">		</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">	@Override</span><br><span class="line">	public Future&lt;V&gt; execute(Callable&lt;V&gt; callable) &#123;</span><br><span class="line">		Object lock = new Object();</span><br><span class="line">		ExecutorThread&lt;V&gt; thread = new ExecutorThread&lt;V&gt;(callable,lock);</span><br><span class="line">		thread.start();</span><br><span class="line">		Future&lt;V&gt; future = new Future&lt;V&gt;() &#123;</span><br><span class="line"></span><br><span class="line">			@Override</span><br><span class="line">			public V get() throws Exception &#123;</span><br><span class="line">				synchronized (lock) &#123;</span><br><span class="line">					//通过锁机制，使得未完成时，get方法陷入等待队列，让出cpu给别的线程，异步完成时再唤醒</span><br><span class="line">					//需持有锁才能调用<span class="built_in">wait</span></span><br><span class="line">					<span class="keyword">while</span>(!thread.isDone) &#123;</span><br><span class="line">						lock.wait();</span><br><span class="line">					&#125;</span><br><span class="line">					<span class="keyword">if</span>(thread.e != null) &#123;</span><br><span class="line">						throw thread.e;</span><br><span class="line">					&#125;</span><br><span class="line">					<span class="built_in">return</span> thread.result;</span><br><span class="line">				&#125;</span><br><span class="line">			&#125;</span><br><span class="line">			</span><br><span class="line">		&#125;;</span><br><span class="line"></span><br><span class="line">		<span class="built_in">return</span> future;</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<h2 id="总结"><a href="#总结" class="headerlink" title="总结"></a>总结</h2><p>优点:通过多线程执行并立即返回一个Future对象,而不等待任务，使得源线程继续执行，<br>只有当源线程需要多线程执行结果，调用其get方法时，通过创建执行线程时创建的对象锁来阻塞线程直到任务执行完成<br>当执行过程中如果有抛出异常,则先捕获该异常，在调用get执行结果时再抛出</p>
<h3 id="请移步"><a href="#请移步" class="headerlink" title="请移步"></a>请移步</h3><p>个人主页: <a href="http://yangyitao.top" target="_blank" rel="noopener">yangyitao.top</a></p>

      
    </div>
    
    <div class="article-info article-info-index">
      
      
      

      
      <div class="clearfix"></div>
    </div>
      
    
  </div>
  
</article>







  
    <article id="post-JUC相关" class="article article-type-post" itemscope itemprop="blogPost">
  
    <div class="article-meta">
      <a href="/blog/2019/03/23/JUC相关/" class="article-date">
  	<time datetime="2019-03-23T01:36:36.204Z" itemprop="datePublished">2019-03-23</time>
</a>
    </div>
  
  <div class="article-inner">
    
      <input type="hidden" class="isFancy" />
    
    
      <header class="article-header">
        
  
    <h1 itemprop="name">
      <a class="article-title" href="/blog/2019/03/23/JUC相关/">
        JUC相关
        
      </a>
    </h1>
  

      </header>
      
    
    <div class="article-entry" itemprop="articleBody">
      
        <p>欢迎查看Eetal的第八篇博客–JUC相关</p>
<h2 id="JUC"><a href="#JUC" class="headerlink" title="JUC"></a>JUC</h2><p>JUC是java.util.concurrent的简写,该包下包含一系列java关于多线程协作相关的类</p>
<h2 id="notify和wait"><a href="#notify和wait" class="headerlink" title="notify和wait"></a>notify和wait</h2><p>notify和wait为Object的方法,需要当前线程持有该对象锁,没有调用则会排除非法监管状态的异常,wait使得当前线程放弃该对象锁,进入条件等待队列,notify从该对象锁的条件等待队列中唤醒一个线程，使其进入对象锁的竞争队列</p>
<h2 id="可重入锁和不可重入锁区别"><a href="#可重入锁和不可重入锁区别" class="headerlink" title="可重入锁和不可重入锁区别"></a>可重入锁和不可重入锁区别</h2><p>可重入锁使得一个线程内执行的同锁方法之间的调用不需要重新获取锁，比如对象锁—某个对象中的实例方法的互相调用</p>
<h2 id="Lock相关"><a href="#Lock相关" class="headerlink" title="Lock相关"></a>Lock相关</h2><p>lock()方法请求锁,如果获取失败则阻塞直到获取成功<br>unLock()方法释放锁,需要拥有锁才可调用，否则抛出异常<br>tryLock()方法，尝试获取锁,不阻塞,立即返回，获取成功返回true，获取失败返回false</p>
<h2 id="Lock—Condition"><a href="#Lock—Condition" class="headerlink" title="Lock—Condition"></a>Lock—Condition</h2><p>通过lock.newCondition()方法获得，代表一个条件<br>类似于Object的notify和wait<br>condition.await() == object.wait()<br>condition.signal() == object.notify()</p>
<h2 id="Lock与synchonized"><a href="#Lock与synchonized" class="headerlink" title="Lock与synchonized"></a>Lock与synchonized</h2><p>synchonized不支持响应中断<br>Lock可以响应中断，但需要编码完成细节</p>
<h3 id="请移步"><a href="#请移步" class="headerlink" title="请移步"></a>请移步</h3><p>个人主页: <a href="http://yangyitao.top" target="_blank" rel="noopener">yangyitao.top</a></p>

      
    </div>
    
    <div class="article-info article-info-index">
      
      
      

      
      <div class="clearfix"></div>
    </div>
      
    
  </div>
  
</article>







  
  
    <nav id="page-nav">
      <a class="extend prev" rel="prev" href="/blog/">&laquo; Prev</a><a class="page-number" href="/blog/">1</a><span class="page-number current">2</span><a class="page-number" href="/blog/page/3/">3</a><a class="extend next" rel="next" href="/blog/page/3/">Next &raquo;</a>
    </nav>
  
</div>
      <footer id="footer">
  <div class="outer">
    <div id="footer-info">
      <div class="footer-left">
        &copy; 2019 Eetal
      </div>
        <div class="footer-right">
          <a href="http://hexo.io/" target="_blank">Hexo</a>  Theme <a href="https://github.com/smackgg/hexo-theme-smackdown" target="_blank">Smackdown</a>
        </div>
    </div>
  </div>
</footer>
    </div>
    
  <link rel="stylesheet" href="/blog/fancybox/jquery.fancybox.css">


<script>
	var yiliaConfig = {
		fancybox: true,
		mathjax: true,
		animate: true,
		isHome: true,
		isPost: false,
		isArchive: false,
		isTag: false,
		isCategory: false,
		open_in_new: false
	}
</script>
<script src="/blog/js/main.js"></script>



<script type="text/x-mathjax-config">
MathJax.Hub.Config({
    tex2jax: {
        inlineMath: [ ['$','$'], ["\\(","\\)"]  ],
        processEscapes: true,
        skipTags: ['script', 'noscript', 'style', 'textarea', 'pre', 'code']
    }
});

MathJax.Hub.Queue(function() {
    var all = MathJax.Hub.getAllJax(), i;
    for(i=0; i < all.length; i += 1) {
        all[i].SourceElement().parentNode.className += ' has-jax';                 
    }       
});
</script>

<script src="//cdn.bootcss.com/mathjax/2.7.0/MathJax.js"></script>


  </div>
</body>
</html>